Section 5.2. B-tree in SQLite
Table and Index Management > B+-tree in SQLite
5.2. B+-tree in SQLite
A tree is created by allocating its root page. The root page is not relocated. Each tree is identified by its root page number. The number is stored in the master catalog table, whose root always resides on Page 1.
Figure 5-2. A typical B+-tree
SQLite stores tree nodes (both internal and leaf) in separate pages one node in one page (see Figure 5-2).The pages are accordingly referred to as internal and leaf pages, respectively. For each node, the key and data for any entry are combined to form a payload. A fixed preset amount of payload is stored directly on the page. If the payload is larger than the amount, then surplus bytes are spilled into overflow pages: excess payload is sequentially stored in a linked list of overflow pages. Internal nodes, not shown in the figure, can have overflow pages, too.
