Firebird Documentation IndexInside a Firebird Database → Index B-Tree Page - Type 0x07 - YOU ARE HERE.
Firebird Home Firebird Home Prev: Index Root Page - Type 0x06Firebird Documentation IndexUp: Inside a Firebird DatabaseNext: Blob Data Page - Type 0x08 - TODO

Index B-Tree Page - Type 0x07 - YOU ARE HERE.

B-Tree Header
Index Jump Info
Index Jump Nodes
Index Nodes
Index Data

As described above for the Index Root Page (type 0x06) each index defined for a table has a root page from which the index data can be read etc. The Index Root Page field irt_root points to the first page (the root page - just to confuse matters slightly) in the index. That page will be a type 0x07 Index B-Tree Page, as will all the other pages that make up this index.

Indices do not share pages. Each index has its own range of dedicated pages in the database. Pages are linked to the previous and next pages making up this index.

B-Tree Header

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:

  • Bit 0 : set means do not garbage collect this page.

  • Bit 1 : set means this page is not propogated upwards.

  • Bit 3 : set means that this page/bucket is part of a descending index.

  • Bit 4 : set means that non-leaf nodes will contain record number information.

  • Bit 5 : set means that large keys are permitted/used.

  • Bit 6 : set means that the page contains index jump nodes.

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.

Index Jump Info

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.

Index Jump Nodes

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
};

Index Nodes

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.

Index Data

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!
Prev: Index Root Page - Type 0x06Firebird Documentation IndexUp: Inside a Firebird DatabaseNext: Blob Data Page - Type 0x08 - TODO
Firebird Documentation IndexInside a Firebird Database → Index B-Tree Page - Type 0x07 - YOU ARE HERE.