The directory and the tables that map context names, keywords and titles are B+ trees with one layout. A tree is a 38-byte header and then fixed-size pages. Each entry is laid out as the header’s structure string says.
0Header the magic number, page size, structure string, root page, page count and entry count38 bytes38Pages numbered from 0, in any order: index pages down to leaf pagesPageSizeeach
Header
| Offset | Size | Type | Name | Description |
|---|---|---|---|---|
| 0 | 2 | u16 | Magic | Always 0x293B |
| 2 | 2 | u16 | Flags | Bit 0x0400 is set for the directory; bit 0x0002 is always set |
| 4 | 2 | u16 | PageSize | 1,024 bytes for the directory, usually 2,048 for the other trees |
| 6 | 16 | char | Structure | What an entry holds; see below |
| 22 | 2 | i16 | MustBeZero | Always 0 |
| 24 | 2 | i16 | PageSplits | How many times a page split while the tree was built |
| 26 | 2 | i16 | RootPage | The page where a search starts |
| 28 | 2 | i16 | MustBeNegOne | Always −1 |
| 30 | 2 | i16 | TotalPages | The number of pages |
| 32 | 2 | i16 | NLevels | The number of levels, leaves included |
| 34 | 4 | u32 | TotalBtreeEntries | The number of entries in the tree |
Structure string
Each character of the string describes one field of a leaf entry, in order. The first field is the key.
| Char | Field |
|---|---|
L, 4 | A 32-bit number |
2 | A 16-bit number |
z, F, i | A NUL-terminated string |
! | A 32-bit byte count and then that many bytes |
The directory is z4: a name and an offset.
Pages
A search starts at RootPage. An index page lists keys with the page to
follow for them, and its header gives the page for keys before its first. After
NLevels − 1 index pages the search reaches a leaf. Leaf pages are
chained, so a whole tree can be read in key order by following the chain.
| Offset | Size | Type | Name | Description |
|---|---|---|---|---|
| 0 | 2 | u16 | Unused | Free bytes at the end of the page |
| 2 | 2 | i16 | NEntries | The entries on this page |
| 4 | 2 | i16 | PreviousPage | Leaf page: the previous leaf, or −1. Index page: the child for keys before the first entry |
| 6 | 2 | i16 | NextPage | Leaf pages only: the next leaf, or −1 |
Leaf entries follow at offset 8, one after another as the structure string says. Index pages have their entries at offset 6: a key, then a 16-bit page number.