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

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

by jvns • 12 years ago

58 4 12 years ago

...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?

petergeoghegan2• 12 years ago

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• 12 years ago

I think she means the latter.

petergeoghegan2• 12 years ago

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).

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

Related Stories