Everything in an ESE database is a B+-tree of pages: each table, each index, each table's long values and the catalog itself. A tree is named by its root page, whose number the catalog gives. Records live only in the leaves; branch pages hold keys and the numbers of their children. All the leaves of one level are linked left to right by the previous and next page numbers in the page header.
Walking and searching
| To | Do |
|---|---|
| Read every entry in key order | From the root go to the first entry's child, again and again, until a page is a leaf (flag 2). Read its entries, then follow next page until it is 0. Skip defunct entries (tag flag 2). |
| Find the entry for a key | On a branch, take the first entry whose key is not smaller than the search key (an entry with an empty key is bigger than everything) and go to its child. On the leaf, take the first entry whose key is not smaller; if every key on the leaf is smaller, the entry starts the next leaf. |
| Count the entries | On every leaf, count the tags after tag 0 that have a size and no defunct flag. |
Keys are compared as unsigned bytes, a shorter key being smaller when it is the start of a longer one.
Root header
The first value (tag 0) of a root page is the root header. It is 16 bytes, or 25 in files that have the longer form:
| 16-byte form | 25-byte form | Name | Description |
|---|---|---|---|
| 0 | 0 | Initial number of pages | How many pages the tree started with. |
| 4 | Unknown | One byte. | |
| 4 | 5 | Parent father data page | The object identifier of the parent tree: the table, for an index or a long value tree. |
| 8 | 9 | Extent space | 0: the tree's pages are one extent starting at the root page. 1 or more: the pages are listed by space trees. |
| 12 | 13 | Space tree page number | The root of the owned-pages tree; the available-pages tree is the next page. Valid when the extent space is not 0. |
| 17 | Unknown | Two 32-bit numbers. |
Entries
A non-root page's tag 0 is the common key: bytes that the keys of its entries may share. Every other value is an entry:
| Field | Size | Description |
|---|---|---|
| Common key size | 2 | Only when the tag's flag 4 is set: how many bytes of the page's common key start this key. Otherwise 0. |
| Local key size | 2 | The length of the key bytes stored in this entry. |
| Local key | variable | The rest of the key. The whole key is the first common key size bytes of the common key, then these. |
| Data | variable | In a branch: four bytes, the child page number. In a leaf: a record (table), the record's key (index), a segment of a long value, or a four-byte page count (space tree). |
A branch entry's key is the last key found below its child, and the last entry of a branch level may have an empty key. Branch pages directly above the leaves have the parent flag (4) set. Table keys are the primary key columns in a normalised form: numbers are big-endian with the sign bit flipped behind a one-byte prefix, so that comparing bytes orders them as numbers.
Links
Reference
- Extensible Storage Engine (ESE) Database File (EDB) format – root header, branch and leaf pages