MySQL为什么选择B+Tree做索引

MySQL为什么选择B+Tree?

首先理解MySQL索引的几个原则

索引是什么？

是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。

工作机制

如上图：以id创建索引，索引数据结构里存储了索引键（关键字）以及对应的值（地址值），当搜寻id=101的数据时，直接找到对应的地址0x123456。时间复杂度为O(1)。

二叉查找树

时间复杂度

二叉查找树

二叉树测试地址：

https://www.cs.usfca.edu/~galles/visualization/BST.html

二叉树缺点：

二叉树缺点

平衡二叉查找树

平衡二叉查找树

每一个节点与子节点的高度差不能大于1。

平衡二叉树测试地址：

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

二叉树缺陷：

搜索时IO次数过多，节点数据内容太多。

多路平衡二叉树（B树）

多路平衡二叉树

多路平衡二叉树测试地址：

https://www.cs.usfca.edu/~galles/visualization/BTree.html

经常变化的字段不要建索引，对B树的维护不好。B树的合并和分裂对性能有损耗。

B+Tree

B+Tree

左闭合区间，id从小到大的递增。数据变动可能是最右边的变动 。

MySQL使用B+Tree的原因：

1. B+Tree扫库、扫表能力更强。
2. B+Tree的磁盘读写能力更强。
3. B+Tree的排序能力更强。
4. B+Tree的传效率更稳定。

MySQL文件存储

两种类型的表：

两种类型的表

两种表的存储文件类型：

存储的文件

索引用Hash算法的缺点：

• 无法范围查询
• 无法排序

InnoDB引擎存储节点的规则

InnoDB采取的⽅式是：将数据划分为若⼲个⻚，以⻚作为磁盘和内存之间交互的基本单位，InnoDB 中⻚的⼤⼩⼀般为 16 KB。也就是在⼀般情况下，⼀次最少从磁盘中读取16KB的内容到内存中，⼀次最少把内存中的16KB内容刷新到磁盘中

我们的实际⽤户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶⼦节点或叶节点，其余⽤来存放⽬录项的节点称为⾮叶⼦节点或者内节点，其中B+树最上边的那个节点也称为根节点。

假设所有存放⽤户记录的叶⼦节点代表的数据⻚可以存放100条⽤户记录，所有存放⽬录项记录的内节点，代表的数据⻚可以存放1000条⽬录项记录，那么：

• 如果B+树只有1层，也就是只有1个⽤于存放⽤户记录的节点， 最多能存放100条记录。
• 如果B+树有2层，最多能存放1000×100=100000条记录。
• 如果B+树有3层，最多能存放1000×1000×100=100000000条记录。