1

我对 B-Tree 概念相当陌生，我目前正在阅读可以在这里找到的课程的幻灯片： http ://www-db.deis.unibo.it/courses/TBD/Lezioni/02%20 -%20 指数.pdf

我读到 B 树的“最小占用率”为 50%。

这意味着什么？这是最低入住率的好百分比吗？更高/更低的最低入住率更好吗？

谢谢

4

1 回答 1

0

这个答案适用于 ENGINE = InnoDB。

出于所有实际目的，给定的 BTree 要么是“满的”，要么是 69% 满的。这不涉及单个块。

单个块...

  • 最初以 key order加载 BTree时，它​​将被填充到 15/16。

  • “最后一个”块可能几乎是空的——假设插入认为树被附加到。

  • 随机填充时，会出现块拆分，使两个连续的块各占 50% 左右。

  • 从长远来看（不断流失和/或添加）BTree，它稳定到平均约 69%。（这是关于 BTree 的事实。）

  • 在事务处理过程中，可能会在块中放置额外的行副本；清理后，这些就消失了。

  • 当两个相邻的块小于半满时，代码可能会尝试合并这些块。

  • InnoDB 预先分配块，因此某些块（在任何时候）是完全空的。

一些数据库供应商为最小/最大/等占用率提供各种可调参数。MySQL遵循KISS原则；没有什么可调整的。效果是 BTree 相当有效。此外，请注意，索引中的选择有限（对于 InnoDB）：

  • 是唯一的PRIMARY KEY和聚集的；这里没有选项。
  • 二级索引（如果有）是非聚集的，并且PRIMARY KEY在叶节点中有列。也就是说，要通过辅助键定位整行，有两个 BTree 向下钻取。

经验法则（对于 InnoDB 的 16KB 块）：BTree 的每个节点中大约有 100 个项目。推论：一个万亿行的表或索引在 BTree 中将有大约6 个级别。（现在，这一段不是比链接中的那些公式等简单吗？）

InnoDB 采用“B+Trees”，因此顺序扫描可以从一个叶子节点走到下一个叶子节点。

另请参阅 Wikipedia 以了解 BTrees 的另一个讨论。

哦，回到关于 50% 的问题——那是“自然的”。想想“块分割”（又名“叶子分割”）做了什么——取一个完整的块并将其变成两个相邻的半完整块。要求 50% 以外的任何东西都是没有意义的。（是的，你可以将一个完整的块分成 3 个，但这似乎很浪费。或者你可以在它完全填满之前拆分，但这样做并没有什么好处。）

于 2018-07-11T18:28:37.367 回答