Author seems to have just backed into rediscovering B-trees https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree > To conclude, binary tr

Author seems to have just backed into rediscovering B-trees https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree > To conclude, binary trees are optimal when we ignore the cost of accessing a node, but they aren’t when it becomes costly to access a node. When we access the nodes on disk, with a high cost, it becomes interesting to bundles many keys in a node, and we gave the optimal solution. However, the problem is often solved quite more directly. We just fit as many keys as possible in an I/O block. Disks operates on small blocks of (typically) 512 bytes, but file systems operate in somewhat larger, but fixed-sized blocks, something like 4 or 8k. A good strategy is therefore to fit as many keys as possible in that block, since even if the number of comparisons is large, it will still be faster than bringing that block into main memory.