Skip to content

B-Tree nodes split by entry count, not size: long keys overflow a node page mid-insert #217

Open

Description

@CaffeinatedCoder

BTreeIndex splits a node only when EntryCount >= MaxEntriesPerNode (64); InsertIntoLeaf never checks how many bytes are left in the page. With variable-length keys, a node can fill its page before it reaches 64 entries, and the next insert throws ArgumentOutOfRangeException from the span writes.

Repro (16 KB pages, a DynamicCollection with a B-Tree index on a string field, values {5-digit prefix}{N × 'x'}, one auto-commit insert each):

  • N = 100: 200 inserts succeed
  • N = 400: fails after 39 inserts
  • N = 2000: fails after 8 inserts

Typed indexes hit it sooner, because their keys also carry the document id.

A key length is safe in general only if 64 entries of that length fit in a page: about (PageSize - 52) / 64 - 10 bytes, which is 245 on 16 KB pages and 117 on 8 KB. Since #204 (#185) the failure rolls the transaction back, so the data stays consistent, but the insert still fails, and any index whose keys exceed that bound will eventually fail.

Suggested fix: split by size as well as by count, i.e. split when the new entry doesn't fit in the remaining page space, and do the same for internal nodes. Rejecting long keys up front would be a breaking alternative.

Activity

  1. added
    bugSomething isn't working
    and removed on Oct 15, 2026
  2. added this to the 5.3.0 milestone on Oct 15, 2026
  3. added
    area/indexingB-Tree and secondary indexes, index lifecycle
    severity/highWrong results, crash or failed writes in a realistic scenario
    priority/P1Must be in the next minor release
    on Oct 15, 2026
  4. moved this from Todo to In Progress in BLiteon Oct 15, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    area/indexingB-Tree and secondary indexes, index lifecyclebugSomething isn't workingpackage/coreAffects BLite.Corepriority/P1Must be in the next minor releaseseverity/highWrong results, crash or failed writes in a realistic scenario

    Type

    No type

    Projects

    • Status
      In Progress

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions