wire / wire-format / btree
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.
aka: B-tree (balanced search tree)
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.
| field | size | meaning |
|---|---|---|
| Node structure | variable | Each 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) | config | Each 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. |
| Search | O(log n) | Binary search within node, then recurse to child. O(log_t n) node accesses. |
| Insert | O(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. |
| Delete | O(log n) | Find key, remove. If node underflows (< t-1 keys), borrow from sibling or merge with sibling. May cascade to root. |
| B+ tree | variant | All 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* tree | variant | Nodes are 2/3 full before splitting (vs 1/2 for B-tree). Reduces splits. |
example:
00 00 00 00
B-tree (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/btree
or /wire-format/btree.json