b树中的最小占用率是多少?

xu3bshqb  于 2021-06-21  发布在  Mysql
关注(0)|答案(1)|浏览(423)

我对b-tree的概念还比较陌生,我正在阅读一个课程的幻灯片,可以在这里找到:http://www-db.deis.unibo.it/courses/tbd/lezioni/02%20-%20indices.pdf
我读到b-树的“最低占有率”是50%。
那是什么意思?这是最低入住率的好百分比吗?最低入住率高/低是否更好?
谢谢

ilmyapht

ilmyapht1#

这个答案适用于engine=innodb。
在所有实际应用中,给定的btree要么是“满的”,要么是69%满的。这不涉及单个块。
单个块。。。
最初按键顺序加载btree时,它将填充到15/16 full。
“last”块几乎可以是空的——假设insert认为树是被附加到的。
当随机填充时,会有块分裂,留下两个连续的块,每个块的填充率约为50%。
从长远来看(持续的搅动和/或添加)一个btree,它的平均值稳定在69%左右(这是关于btrees的一个事实。)
当事务进行到中间时,行的额外副本可以放在块中;清理之后,这些就消失了。
当两个相邻的块小于半满时,代码可以尝试合并这些块。
innodb预先分配了块,所以有些块(在任何时候)是完全空的。
一些数据库供应商为min/max/etc占用率提供了各种各样的可调参数。mysql遵循kiss原则;没有可调的。其效果是btrees相当有效。此外,请注意,索引的选择是有限的(对于innodb):
这个 PRIMARY KEY 具有独特性和集群性;这里没有选择。
二级索引(如果有)是非聚集的,并且具有 PRIMARY KEY 叶节点中的列。也就是说,要通过辅助键定位整行,有两个btree向下钻取。
经验法则(对于innodb的16kb块):btree的每个节点中大约有100个条目。推论:一个万亿行的表或索引在btree中大约有6个级别(现在,这一段不是比你链接中的公式更简单吗?)
innodb采用“b+树”,因此顺序扫描可以从一个叶节点走到下一个叶节点。
关于btrees的另一个讨论,请参见wikipedia。
哦,回到50%的问题上来——那是“自然的”。想想“块分割”(又名“叶分割”)是怎么做的——取一个完整的块,把它变成两个相邻的半完整块。只要求50%是没有意义的(是的,你可以把一个街区分成3个街区,但那看起来很浪费。或者你可以在它完全填满之前分开,但这样做不会有什么好处。)

相关问题