B-trees[1] are pretty fast to iterate through as long as the branching factor is fairly large. If the branching factor is 100, you would only need to chase one

B-trees[1] are pretty fast to iterate through as long as the branching factor is fairly large. If the branching factor is 100, you would only need to chase one pointer every 100 nodes (and in practice, even larger branching factors are common). They wouldn't be used so heavily in filesystems and databases if they were slow to iterate through. [1] https://en.wikipedia.org/wiki/B%2B_tree https://en.wikipedia.org/wiki/B%2B_tree