B+TREE BASICS(9)

🌸 B+Tree basics 🌸

okay so bestie, welcome to the B+Tree basics(9) page from the Kernel API Manual — this is the kernel data-structure tea you need. A B+Tree is a data structure for looking up arbitrary keys into pointers, and rn “arbitrary” currently allows unsigned long, u32, u64 and 2 * u64 keys. The data structure is described at https://en.wikipedia.org/wiki/B-tree, and real talk: we currently do not use binary search to find the key on lookups. no cap 💅

Each B+Tree consists of a head, which contains bookkeeping information, plus a variable number of nodes — starting with zero, bestie. Each node contains the keys and pointers to sub-nodes, or, for leaf nodes, the keys and values for the tree entries. iconic ✨

Each node in this implementation has the following layout:

[key1, key2, ..., keyN] [val1, val2, ..., valN]

Each key here is an array of unsigned longs, geo->no_longs in total. The number of keys and values (N) is geo->no_pairs. slay 🦋

👀 SEE ALSO 👀

• Kernel file ./include/linux/btree.h
• struct btree_head(9)
• btree_alloc(9)
• btree_free(9)
• btree_init_mempool(9)
• btree_init(9)
• btree_destroy(9)
• btree_lookup(9)
• btree_insert(9)
• btree_update(9)
• btree_remove(9)
• btree_merge(9)
• btree_last(9)
• btree_get_prev(9)

mwah 💋 — source/version: ./include/linux; date: October 2026; page: B+Tree basics(9) 🫶