CODEWITHSUNDEEP
databasenosql
Andrew
Andrew

Reputation: 749

Implementing a Graph Based DB

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.

Upvotes: 1

Views: 623

Answers (1)

Andrew
Andrew

Reputation: 749

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.

Upvotes: 2

Related Questions