[mdb-dev] Jet4 index page format notes

[John C. <jfc@MIT.EDU>]

HACKING documents the Jet3 format index page only.  Here is
the description of the Jet4 index.

Jet4 index page

1 byte type (0x03 for higher level index, 0x04 for leaf index)
1 byte 0x01
2 bytes free space*
4 bytes parent page
4 bytes 0x00000000
4 bytes previous page
4 bytes next page
4 bytes overflow page (lower level index page)
1 byte compression level
1 byte 0x00
1 byte index level (0 = leaf)
452 bytes index bitmap, as in Jet3 but covering 3616 bytes
1 byte 0x00 (padding?)
3616 bytes (less free space) index records starting at offset 480 = 0x1e0

Compression: Index records after the first omit the first (compression
level) bytes.  The omitted bytes may span multiple components.  In an
extreme case the compressed records may be only one or two bytes long,
when a non-unique key is repeated many times mapping to rows on the
same page or nearby pages.

Index record format: basically the same as Jet3.

The overflow page is the last leaf page referred to in the "clean up
mode" comment.

*Intermediate index pages are observed to have a real record at the
beginning of the "free space."  This record points at the overflow
page and can be ignored as redundant.

Text index encoding:

Text data	Index encoding
'~'		0x2b, 0x0f (two bytes)
'_'		0x2b, 0x03 (two bytes)
'0'..'9'	0x36..0x48 (even numbers)
'A'		0x4a
'B'		0x4c
'C'..'J'	0x4d..0x5b (odd numbers)
'K'..'Q'	0x5c..0x68 (even numbers)
'R'..'X'	0x69..0x75 (odd numbers)
'Y'		0x76
'Z'		0x78

Encoding is case-insensitive.  Presumably 0x2b introduces a two byte
sequence.

Most text index entries end with 0x01, 0x00 rather than just a null byte.