3 ms·

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

• userbinator 12y 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?
  • petergeoghegan 12y 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 12y ago
    I think she means the latter.
• petergeoghegan 12y ago
  Here is a hacked-together tool for visualizing Postgres B+Trees as GraphViz graphs: https://github.com/petergeoghegan/btree_visualization 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).