B-tree pages, sorted and sparse

So far, the storage internals series has focused on heap pages. We began by opening the 8KB page, then traced MVCC visibility through xmin, xmax, and snapshots. Next we observed HOT updates evade index maintenance, and finally tracked VACUUM as it went through its phases. Each time an index came up, the explanation stopped at either "the index points to the heap via ctid" or "index cleanup removes the dead entries". This chapter is about what lies at the other end of that pointer. B-tree pages use the same 8KB skeleton (24-byte header, line pointers, tuples packed from the bottom up), but where a heap page is an unordered bag of row versions, a B-tree page is sorted and linked to its siblings at the same level. VACUUM cannot undo index bloat for that reason; the operational side of this issue is covered in VACUUM Is a Lie. Index bloat is a recurring topic and source of question during my talk "Postgres Storage Internals Visualized", and this is my attempt to address it better.…

Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town