Data Structures and Algorithms: Linked Lists, Trees, Hash Maps

Dr Jim Webber, Neo4j Chief Scientist, reviews the fundamentals of computer science from university apply to building databases. What are the cheapest data structures for reading? For insertion with limited write contention? For random access? As an amateur arborist, Jim also discusses reading from and writing to trees.

In the next part of this short video, Jim talks about the choice of data structures used for implementing Neo4j. An important property of Neo4j is what we call “index-free adjacency” — Graph traversals in Neo4j are (Pointer Size) * (Offset), which is an O(1) implementation. Of course, we pick and choose other data structures and algorithms for high performance graph storage. We have trees, for example, to implement indexes to find the starting points for graph traversal very affordably. We use lists in Neo4j for scenarios with modest amounts of data to enable high write performance — property chains, as an example.