MySQL B+树深度的了解

https://zhuanlan.zhihu.com/p/444448405

以下从 B+树深度简单模拟计算,有两个主要特征决定了 B 树(或 B+ 树)的深度。

  1. 数据库中的行数。我们将其称为 N。
  2. 索引键的大小。让我们称 B 为适合 B 树节点的键数。(有时 B 用于指代节点大小本身,而不是它持有的键数,但我希望这样看起来更直观。)

给定这些数量,B 树的深度是 log B 为下标 N。那只是 (log N )/log B。现在我们可以注意到小键意味着更大的 B,这会减少 (log N )/log B。如果我们将键的字节大小减半,那么 B 树的深度将从 (log N )/log B 到 (log N )/log 2 B(适合树节点的键数量的两倍),这就是(log N )/(1+log B )。

让我们在那里输入一些数字。假设您有 10 亿行,并且您目前可以在一个节点中容纳 64 个键。那么树的深度是 (log 10^ 9 )/ log 64 ≈ 30/6 = 5. 现在你用一半大小的字节的键重建树,你得到 log 10^9 / log 128 ≈ 30/7 = 4.3。假设树的前 3 个级别在内存中,那么您从平均 2 次磁盘搜索到平均 1.3 次磁盘搜索,加速了 35%。

这是一个很好的节省,当然,假设您使用的新的、较小的键对查询同样有用。插入 B 树的时间也同样节省。插入是 O((log N )/log B ) — 与点查询大致相同,最多为一个常数,但无论如何,您仍然会获得类似的加速。

范围查询呢?这里对树的深度并不那么敏感。但是在范围查询中,您寻找具有第一行的叶子,然后迭代 所有行,根据需要跳转到兄弟叶子,直到到达结束行。寻找第一片叶子的初始时间——这部分取决于树的深度

然而,这里有一个更微妙的效果。如果您有快速插入(例如,通过使用较小的键),您可以保留更多索引。拥有正确的索引可以对范围查询产生巨大的影响:没有索引可能意味着对少量行的范围查询可能变成全表扫描。一旦添加了正确的索引,我已经在此类查询中看到了 多个数量级的加速。

https://alicharles.oss-cn-hangzhou.aliyuncs.com/static/images/mp_qrcode.jpg
文章目录