为什么B树上的随机操作不好？

Question

我阅读了下面的文章并尝试了解数据持久性的不同数据结构。文章中写道，顺序操作适用于 B 树，但不适用于随机操作。

文章链接

请您用一些例子来说明这一点好吗？预先感谢。

Answer 1

顺序键（或单调递增函数）通常不会给 B 树带来问题

也就是说，键值连续（或单调）的访问序列通常不会给 B 树带来问题。

原因如下：在顺序访问期间，键值往往会保留在同一个 B 树节点中，而随机访问可能会不断改变 B 树节点；一个B树节点代表一个二级存储页；因此，前者意味着更改辅助存储页面的频率较低，而后者则意味着更改频率较高；所以前者通常更快，而后者通常更慢。

Answer 2

随机访问操作比顺序操作差的原因隐藏在 B 树的结构中。 B 树节点通常包含一组记录。每个 B 树节点代表非易失性存储的一个实际磁盘块。所以基本上，如果您尝试读取随机记录，它们很可能存储在不同的节点（即不同的块）中，并且您必须进行尽可能多的磁盘 IO。另一方面，在顺序访问的情况下，记录往往存在于相同的块中，因此您将有更少数量的块进行 IO。

顺便说一句，事实证明，当我们谈论纯 B 树时，它们甚至以相当随机的方式存储顺序记录，因此会带来性能问题。这个问题可以通过 B+ 树来解决，它倾向于在叶子节点中顺序存储顺序记录，叶子节点像链表一样相互连接。