How does SQLite work? Part 2: disk seeks are slow don't do them

[jvns]

http://jvns.ca/blog/2014/10/02/how-does-sqlite-work-part-2-btrees/

[userbinator]

...and this is the reason why there's been a proliferation of SSD use especially in the area of database servers.

Each table has a btree, made up of interior and leaf nodes. Leaf nodes contain all the data, and data nodes contain, well, data :)

Anyone else find this paragraph a little confusing? Is she saying interior nodes contain all the data of the tree, or that leaf nodes are data nodes?

[petergeoghegan → userbinator]

The internal nodes point to leaf nodes. The leaf nodes contain pointers to the heap (table). At least with a B+Tree, the internal nodes only point to the leaf nodes in the same B+Tree structure, and not to "data proper".

So the leaf nodes, which are often about 99% of the total, contain index tuples that point to the "data proper". The internal nodes have index tuples too, but those are only used to get to the leaf nodes.

[mercurial → userbinator]

I think she means the latter.

[petergeoghegan]

Here is a hacked-together tool for visualizing Postgres B+Trees as GraphViz graphs: https://github.com/petergeoghegan/btree_visualization

Note that it's very rough, because I never got around to polishing it (I am not really the original author). It also visualizes them in physical as opposed to logical order, because I never finished off the latter (which would probably be more useful).