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

MySQL为什么选择B+Tree?

理解MySQL索引的几个原则

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

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

时间复杂度O($log_2n$)

二叉树测试地址：

二叉树缺点：

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

平衡二叉树测试地址：

二叉树缺陷：

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

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

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

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

MySQL使用B+Tree的原因：

两种类型的表：

两种表的存储文件类型：

索引用Hash算法的缺点：

1.无法范围查询

2.无法排序

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

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

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