wire / wire-format / btree

B-tree (balanced search tree)

A B-tree is a self-balancing tree data structure that maintains sorted data and allows O(log n) search, insert, and delete. Each node has between t-1 and 2t-1 keys (t = minimum degree). All leaves are at the same level. Used in databases (indexes), filesystems (ext4, XFS, Btrfs), and key-value stores.

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: B-tree (balanced search tree)

wire format

spec: B-tree (Bayer & McCreight, 1972)

A B-tree is a self-balancing tree data structure that maintains sorted data and allows O(log n) search, insert, and delete. Each node has between t-1 and 2t-1 keys (t = minimum degree). All leaves are at the same level. Used in databases (indexes), filesystems (ext4, XFS, Btrfs), and key-value stores.

fieldsizemeaning
Node structurevariableEach node: n keys + n+1 child pointers (for internal nodes) or n keys + n+1 record pointers (for leaf nodes). Keys are sorted.
Minimum degree (t)configEach node has at least t-1 keys (except root: at least 1) and at most 2t-1 keys. Each internal node has at least t children and at most 2t children.
SearchO(log n)Binary search within node, then recurse to child. O(log_t n) node accesses.
InsertO(log n)Find leaf, insert key. If node is full (2t-1 keys), split it (median key moves up to parent). May cascade to root.
DeleteO(log n)Find key, remove. If node underflows (< t-1 keys), borrow from sibling or merge with sibling. May cascade to root.
B+ treevariantAll data in leaves; internal nodes only store keys for routing. Leaves linked in a doubly-linked list for range scans. Used by most databases.
B* treevariantNodes are 2/3 full before splitting (vs 1/2 for B-tree). Reduces splits.

example:

00 00 00 00

B-tree (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/btree or /wire-format/btree.json