MySQL BTREE索引

发布网友发布时间：2022-10-04 21:44

我来回答

共1个回答

热心网友时间：2023-10-15 23:18

个人能力有限，如有错误请指出，共同学习。

二叉树

B树

B+树

特点：

聚簇索引

二级索引

key数据存储量估算：
若每个页可以存1000个key，而且树的高度是4，那么

前提条件如下：

插入步骤
步骤一
因为索引中还没有数据，所以此时的B+树只有一个空的根结点，又由于一个页只能存3个key，首先将10，20，5插入进去（实际上此步发生了3次插入），然后在页面内做数据排序，最终结果如下图：

步骤二：
由于根页面已经写满，此时插入8，将发生*（根页面*），大致步骤如下：
注意：在*过程中，根结点始终是不会变的，不管变成多大的树，根结点的页面号始终如一。

步骤五：
插入数据40，发现比根结点23大，找到103号页面，发现已满，执行*，*同上面叶子结点的*步骤。*后如图所示：

步骤六：
继续插入下一个数据9，因为比20小，找到101号页面，发现已满，需要做叶子结点*，如下图：

传统B+树的数据删除，一般都会有一个所谓的填充因子，来控制页面数据的删除比例，如果数据量小于这个填充因子所表示的数据量，就会有节点合并，这与*是相对应的。
InnoDB的实现与传统B+树算法有不同之处，InnoDB在删除索引数据时，会先检查当前页剩余的记录数，如果只剩下一条记录，就会直接将这个页面从B+树中摘除，也只有这种情况，InnoDB才会回收一个页面，InnoDB的页面没有合并一说，但是对于根节点，即使索引数据全部删除，根节点页依然存在，只不过是以空页的形式存在。
下面举个例子描述索引删除过程，前提条件与前面插入记录时一致。

删除数据 50

删除过程全部结束，最终得到一个空的索引页。

《MySQL运维内参》
B+树动画演示： https://www.cs.usfca.e/~galles/visualization/BPlusTree.html