Use a B-tree with fanout \sqrt{B}.