How does I/O work for large graph databases?

Question

I should preface this by saying that I'm mostly a front end web developer, trained as a musician, but over the past few years I've been getting more and more into computer science.

So one idea I have as a fun toy project to learn about data structures and C programming was to design and implement my own very simple database that would manage an adjacency list of posts. I don't want SQL (maybe I'll do my own query language? I'm just having fun). It should support ACID. It should be capable of storing 1TB let's say.

So with that, I was trying to think of how a database even stores data, without regard to data structures necessarily. I'm working on linux, and I've read that in that world "everything is a file," including hardware (like /dev/*), so I think that that obviously has to apply to a database, too, and it clearly does--whether it's MySQL or PostgreSQL or Neo4j, the database itself is a collection of files you can see in the filesystem.

That said, there would come a point in scale where loading the entire database into primary memory just wouldn't work, so it doesn't make sense to design it with that mindset (I assume). However, reading from secondary memory would be much slower and regardless some portion of the database has to be in primary memory in order for you to be able to do anything with it. I read this post:

Why use a database instead of just saving your data to disk?

And I found it difficult to understand how other databases, like SQLite or Neo4j, read and write from secondary memory and are still very fast (faster, it would seem, than simply writing files to the filesystem as the above question suggests). It seems the key is indexing. But even indexes need to be stored in secondary memory. They are inherently smaller than the database itself, but indexes in a very large database might be prohibitively large, too.

So my question is how is I/O generally done with large databases like the one I described above that would be at least 1TB storing a big adjacency list? If indexing is more or less the answer, how exactly does indexing work--what data structures should be involved?

Answer 1

I think the term you're looking for is Memory-mapped file. The Neo4j devs occassionally blog about Neo4j internal, the post Neo4j Internals: Persistence and Memory Mapping should be of interest. Haven't read it myself though and I'm not sure how current it is w.r.t. to Neo4j implementation (post is from 2010), but it could be a starting point.

Answer 2

This is hard…

To read a block from disk takes a long time, even on a SSD reading a block takes time. However a block can hold many objects and links to other objects. So you wish to put object that tend to get accessed at the same time on the same disk/ssd block.

A long time ago I worked on a system used for map production, that stored roads, houses etc as object with links between them. We created our object ID using prefix that was based on the graphical location of the object (using a gray code), and then stored then in a B+ tree.

(A normal database will be all houses in one table, all roads in anther table, etc. It will then try to put each table onto a different section of disk.)