1

I am designing a project where students would have to implement their own graph based database.

Is there any definitive resource that compares the data structures for implementing a graph based database?

Unfortunately there does not seem to be a resource that compares or recommends the data structure(s) and algorithms to be used for this kind of database. In a typical RDBMS, for example, you would expect to use a B+ tree or something similar.

I would like to know whether there is a good, well-known approach to implementing such a database.

Improve this question

1 Answer 1

Reset to default
2

After some additional research I finally came across a book that describes how Neo4j is implemented.

The most important concept in Graph Based databases is the concept of index-free adjacency. That is, the adjacency list of the node needs to be kept with the node; this avoids having to search for the adjacency list using trees once you have the node, making Graph Based databases faster for handling graphs.

Also, it is important to remember that both the nodes and the relationships require to store information.

It is not surprising that the way that the information is stored is through adjacency lists. Both nodes involved in a relationship will store a doubly linked of relationships.

Physical storage of data in Neo4j reproduced from the book Graph Databases by Ian Robinson et al.

It is my opinion that instead of a doubly linked list, some alternate structure to store the adjacency list can be used (the choice depends on the scenario being tackled). For example, a self-organising linked list if some relationships are accessed more often than others, or a some sort of tree structure for the adjacencies, if you are expecting nodes to have a large amount of relationships.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Hi, what was the book that you referred to in this answer?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.