mysql索引主要基于Hash表和B+树，因为树的查询效率高且可以保持有序，为啥mysql没有采用二叉树？
主要考虑磁盘IO,数据库索引树存储在磁盘的，数据量大时，索引的量同样很大，因此在利用索引查询的时候不能加载全部索引，只能逐一加载每一个磁盘页(对应索引树节点)。
1.1、二叉树
重要的数据结构，存储结构及算法都较为简单，其特点是每个节点最多只能有两颗子树，且有左右之分。
满二叉树
所以节点都有两个子节点，且叶子节点都在树的最下层(完全二叉树特殊情况)
图 1
完全二叉树
叶子节点只能出现在最下层以及次下层，且最下层叶子节点只出现在左边（满二叉树一定是完全二叉树）
图 2
1.2、二叉树的遍历(以图2为例)
先序遍历
根左右
遍历结果：30,25,19,10,22,27,26,28,37,35,40
中序遍历
左根右
遍历结果：10,19,22,25,26,27,28,30,35,37,40（按照水平顺序即可）
后序遍历
左右根
遍历结果：10,22,19,26,28,27,25,35,40,37,30
层序遍历
从上到下，从左到右
遍历结果：30,25,37,19,27,35,40,10,22,26,28
1.3、二叉树作为索引结构情形
索引树结构如图2，查找22，第一次磁盘IO结果：30，第二次磁盘IO结果：25，第三次磁盘IO：结果19，第四次磁盘IO拿到，可看出磁盘IO最坏情况是树的高度。因此高度矮的树可以减少磁盘IO次数
2.1、B-树
一种平衡查找树，每一个节点最多包含k个孩子，k被称为B树的阶，k的大小取决于磁盘页的大小
k阶B-树特征：
（1）根节点子节点个数[2,k];
（2）中间节点子节点个数[k/2,k]，向上取整;
（3）所有的叶子节点都位于同一层；
图 3
图3中（9,13）节点有三个子节点，8<9、10,12在9-13之间、15大于13，符合特征
2.2、B-树作为索引结构情形
B-树的查询过程，目标10，第一次磁盘IO结果6，第二次磁盘IO结果（9,13），第三次磁盘IO结果（10,12），B-树在查询过程中的查询次数不比二叉树少，但和磁盘IO消耗时间相比，查询耗时就基本可忽略，较少次的磁盘IO，极大提高效率，是B-树的优势之一
2.3、B-树插入操作
图3为3阶B-树，插入11，（10,12）节点无法再增加，父节点（9,13）也无法再增加，根节点是单元素节点可变为二元素节点，于是拆分（10,12）与（9,13），根节点变为（6,11）二元素节点
图 4
2.4、B-树删除操作
在图4基础上删除节点5，3的子节点就只有（1,2）不符合规定，发生右旋，2成为父节点，3成为子节点
图 5
3.1、B+树
B-树的一种变体，查询性能更好，B+树可以理解为B-树和线性的组合。。。。。。（待补充）
3.2、B+树索引与Hash索引的区别
（1）Hash索引不能进行范围查询，Hash索引指向的数据是无序的，B+树叶子节点是有序的链表
（2）Hash索引可以一次定位，效率非常高，不同于B+树需要多次磁盘IO以及查询操作
网友评论