The B-Tree is the most widely used on-disk data structure. PostgreSQL, MySQL InnoDB, SQLite, and virtually every relational database uses B-Trees for their indexes.

A B-Tree node maps to a fixed-size page on disk (typically 4KB, matching the OS page size). Each node holds:

• Internal nodes: sorted keys + child pointers. Each key acts as a separator between two subtrees.
• Leaf nodes: sorted keys + values (or pointers to data rows).

The search algorithm:

1. Start at the root node (1 disk read)
2. Binary search within the node to find the correct child pointer
3. Follow the pointer to the next node (1 disk read)
4. Repeat until reaching a leaf node
5. Binary search within the leaf for the key

With a branching factor of 500 (typical for 4KB pages), a 3-level B-Tree can store ~125 million keys, requiring only 3 disk reads per lookup.

Request:  {"type": "btree_search", "msg_id": 1, "key": "user:42"}
Response: {"type": "btree_search_ok", "in_reply_to": 1, "found": true, "value": "Alice", "disk_reads": 3, "depth": 3}

Request:  {"type": "btree_search", "msg_id": 2, "key": "user:999999"}
Response: {"type": "btree_search_ok", "in_reply_to": 2, "found": false, "disk_reads": 3, "depth": 3}

Request:  {"type": "btree_info", "msg_id": 3}
Response: {"type": "btree_info_ok", "in_reply_to": 3, "depth": 3, "total_nodes": 512, "page_size_bytes": 4096, "branching_factor": 500}