Database Internals Book Notes by Verity Chu, 10 Feb, 2022

discuss some concepts specific to B-Trees.

1. organization: how to establish relationships between keys and pointers, and how to implement headers and links between pages.
2. processes that occur during root-to-leaf descends: how to perform binary search how to collect breadcrumbs and keep track of parent nodes ( in case we later have to split or merge nodes.)
3. optimization techniques (rebalancing, right-only appends, and bulk loading), maintenance processes, and garbage collection.

Page Header

holds information about the page that can be used for navigation, maintenance, and optimizations.

usually contains flags: that describe page contents and layout, number of cells in the page, lower and upper offsets marking the empty space (used to append cell offsets and data), and other useful metadata.

e.g.

Postgres: page size, layout version

MySQL InnoDB: number of heap records, level, some implementation-specific values.

SQLite: number of cells and a rightmost pointer.

Magic numbers

often placed in the file or page header often used for validation and sanity checks Usually, it’s a multibyte block, containing a constant value that can be used to signal that the block represents a page, specify its kind, or identify its version.