server/paged_btree library

Order-preserving B+-tree index built on PagedFile.

Maps binary keys (compared lexicographically via unsigned-byte order) to 64-bit values (typically RowIds from a PagedHeap). Supports point lookup, ordered range scan, insert, and delete — all out-of-core, with one page resident per descent step.

Page layout

Page 0 — header (16 bytes used):

  offset  field
  ------  -----
       0  u32 magic 'DBT1'
       4  u32 root page number
       8  u32 entry count (informational)
      12  u32 reserved

Leaf page (kind = 1):

  offset  field
  ------  -----
       0  u8  kind = 1
       1  u8  reserved
       2  u16 entry count
       4  u32 next-leaf page (0 = end)
       8  packed entries:
            u16 keyLen
            u16 reserved
            u64 value
            keyLen bytes key

Internal page (kind = 2):

  offset  field
  ------  -----
       0  u8  kind = 2
       1  u8  reserved
       2  u16 entry count
       4  u32 leftmost child page
       8  packed entries:
            u16 keyLen
            u16 reserved
            u32 right child page
            keyLen bytes key

Routing: a key k descends to the right child of the largest entry whose key is <= k; if k < first entry key, descend to leftmostChild.

Concurrency

Same as PagedFile / PagedHeap: callers serialise mutators externally. Reads can run concurrently with other reads.