It All Fits In RAM Now

Your team has been quoting the classic argument: a B-tree with fanout 509 finds a key among 10910^9 in 4 block reads, while a balanced binary tree needs about 30, so use the B-tree. Then the machine gets 512 GB of RAM and the entire index is resident. Someone proposes replacing the B-tree with a plain balanced binary tree, arguing the disk argument no longer applies.

What is the strongest response?

A

They are wrong, because a hash table strictly dominates any tree once the data is resident.

B

The argument survives with the units swapped: the transfer unit becomes the cache line rather than the disk block, so a wide node that fills whole cache lines still beats 30 dependent pointer chases through scattered memory.

C

The argument holds unchanged. The external memory model counts transfers of a block of size B, and that accounting says nothing about which medium the block lives on, so the 4 reads against 30 comparison carries over to RAM exactly as it stands.

D

They are right on the numbers. In RAM every access costs the same, so what matters is comparison count, and both structures do about 30 comparisons.