SQLite Internals: Pages & B-trees

Summary

SQLite stores table rows as encoded byte arrays, and understanding that representation explains how a simple database preserves compact records and supports efficient growth. Using a sandwich table as an example, the post decodes a row’s varints, type values, UTF-8 text, IEEE-754 floating-point value, and integer count, then examines 4KB pages, cell-pointer indexes, and page headers. SQLite’s b+tree places records in leaf pages and key-range indexes in interior pages; page splits add levels as the database grows, while searches traverse only one page per tree level. The examples estimate that a depth-four tree can hold about 500³ leaf pages, or roughly 476GB, while requiring four page reads for a lookup. The discussion concludes that integer storage is more space-efficient than floating-point storage and that internals such as record encoding and PRAGMAs become less opaque when understood.

Takeaways

1. 1

   SQLite varints use the high bit as a continuation flag and the remaining seven bits for data, allowing integers such as 1,000 to occupy two bytes instead of eight.

2. 2

   SQLite stores rows in 4KB pages, with cell pointers indexing record offsets while row data is packed from the end of the page backward.

3. 3

   A depth-four b+tree can hold about 500³ leaf pages, or roughly 476GB, while a lookup requires at most four page reads in the example.