The C code representation of an ODS 11 index b-tree page is:

struct btree_page
{
    pag btr_header;
    SLONG btr_sibling;
    SLONG btr_left_sibling;
    SLONG btr_prefix_total;
    USHORT btr_relation;
    USHORT btr_length;
    UCHAR btr_id;
    UCHAR btr_level;
};

Btr_header: The page starts off with a standard page header. The pag_flags byte is used on these pages. The bits used and why are:

Btr_sibling: Four bytes, signed. Bytes 0x10 - 0x13 on the page. This is the page number of the next page of this index. The values on the next page are higher than all of those on this page. A value of zero here indicates that this is the final page in the index.

Btr_left_sibling: Four bytes, signed. Bytes 0x14 - 0x17 on the page. This is the page number of the previous page of this index. The values on the previous page are lower than all of those on this page. A value of zero here indicates that this is the first page in the index.

Btr_prefix_total: Four bytes, signed. Bytes 0x18 - 0x1b on the page. The sum of all the bytes saved on this page by using prefix compression.

Btr_relation: Two bytes, unsigned. Bytes 0x1c and 0x1d on the page. The relation id (RDB$RELATION_ID in RDB$RELATIONS) for the table that this index applies to.

Btr_length: Two bytes, unsigned. Bytes 0x1e and 0x1f on the page. The number of bytes used, for data, on this page. Acts as an offste to the first unused byte on the page.

Btr_id: One byte, unsigned. Byte 0x20 on the page. The index id (RDB$INDEX_ID in RDB$INDICES) for this index.

Btr_level: One byte, unsigned. Byte 0x21 on the page. The index level. Level zero indicates a leaf node.

Following on from the above, at byte 0x22 on the page, is an Index Jump Info structure. This is defined as follows:

struct IndexJumpInfo 
{
    USHORT firstNodeOffset;
    USHORT jumpAreaSize;
    UCHAR  jumpers;
};

FirstNodeOffset: Two bytes, unsigned. Offset 0x00 in the structure. This is the offset, in bytes, to the first of the Index Nodes (see below) on this page.

JumpAreaSize: Two bytes, unsigned. Offset 0x02 in the structure. The value here is the number of bytes left to be used before we have to create a new jump node.

Jumpers: One byte, unsigned. Offset 0x05 in the structure. The running total of the current number of Jump Nodes on this page. There can be a maximum of 255 Index Jump Nodes on a page.

The Index Jump Info structure described above is followed by zero or more Index Jump Nodes. The number to be found is determined by the jumpers value in the Index Jump Info structre. Index Jump Nodes are defined as follows:

struct IndexJumpNode
{
    UCHAR* nodePointer;    // pointer to where this node can be read from the page
    USHORT prefix;        // length of prefix against previous jump node
    USHORT length;        // length of data in jump node (together with prefix this is prefix for pointing node)
    USHORT offset;        // offset to node in page  
    UCHAR* data;        // Data can be read from here
};

Btr_nodes: Index nodes are described below and are used to hold the data for one entry in this index. The C code representation of an entry in the array is:

struct btree_nod
{
    UCHAR btn_prefix;
    UCHAR btn_length;
    UCHAR btn_number[4];
    UCHAR btn_data[1];
};

Btn_prefix: One byte, unsigned. Byte 0x00 in the node. This is the size of the compressed prefix.

Btn_length: One byte, unsigned. Byte 0x01 in the node. This is the size of the data in the index entry.

Btn_number: Four bytes, unsigned. Bytes 0x02 - 0x05 in the node. The page number (or record number) where the data that this index entry represents, is to be found.

Btn_data: The data that makes up the index entry is found at bytes 0x06 onwards in the node.

Following the Index Root Page example, we can now hexdump and inspect the Primary Key index for our example table. We see from the Index Root page that the actual root of the index is on page 0x0513eb in the database. A dump of that page results in the following:

513eb000  07 70 39 30 02 00 00 00  00 00 00 00 00 00 00 00  Standard header
513eb010  00 00 00 00                                       Btr_sibling
513eb014  00 00 00 00                                       Btr_left_sibling
513eb018  1f 00 00 00                                       Btr_prefix_total
513eb01c  d5 00                                             Btr_relation
513eb01e  a6 00                                             Btr_length
513eb020  00                                                Btr_id
513eb021  02                                                Btr_level

This looks like it is the final page in this particular index as it has no siblings, left or right. There also doesn't appear to be much space used on the page as btr_length is showing that only 0xa6 bytes have been used on this page, however, btr_level is 2 so we are not looking at a leaf node. (And we know that this is actually the root node for the entire index since the page we dumped is the root page for the index.)

Following on from the above, we have the various index nodes, starting at offset 0x22, as follows:

to be completed soon!