MySQL的InnoDB索引结构采用B+树,B+树什么概念呢,二叉树大家都知道,我们都清楚随着叶子结点的不断增加,二叉树的高度不断增加,查找某一个节点耗时就会增加,性能就会不断降低,B+树就是解决这个问题的。
B树和B+树
在一棵M阶B树中,每个节点最多有 M-1 个关键字,根节点最少可以只有一个关键字,非根节点最少有 Math.ceil(m/2)-1个关键字,下图是一棵阶数为3的树
看下图我们说说B树的特点,很明显一个节点存储的数据更多了,不需要很高的高度就可以存储更多的数据,把一个节点看作一个磁盘,我们发现查找一个数据时可以减少磁盘IO次数,B树的每个节点都有data域,
看下图我们说说B+树的特点,首先明确一点,B+树是在B树的基础上演化而来的,我们就说不同点,只有叶子节点才有data域,叶子节点包含所有的数据,叶子节点通过指针链接形成双向链表。
B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成,而CPU的速度非常快,所以B树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下B树的高度越小,磁盘I/O所花的时间越少
为什么InnoDB选择B+树而不是B树呢
还是上面两张图,对照着看,我们能够得出一下结论
B+树的磁盘读取代价低, 树每个节点都有data域,B+树只有叶子节才有,假设每个节点大小16KB,那么B+树比B树能存储更多的关键字,一次性读入内存的关键字的内存也会更多,B+树的高度也会比B树低,磁盘IO次数会更少。
B+树对范围查询更友好,方便遍历,B树叶子节点没有链接,而B+树叶子节点通过双向指针链接,可以很方便的进行范围查询,比如where条件中 age >=3 and age <20,,那么当找到3时就可以顺着指针找到20,而B树是不可以的。
B+树查询效率稳定性更好, 在B+树中,由于分支节点并不是最终指向文件内容的节点,分支节点只是叶子节点的索引,所以对于任意关键字的查找都必须从根节点走到分支节点,所有关键字查询路径长度相同,每个数据查询效率相当。而对于B树而言,其分支节点上也保存有数据,对于每一个数据的查询所走的路径长度是不一样的,效率也不一样,B树稳定性不如B+树好
我们仔细想想我们SQL常见的查询中,总结起来是不是也就是等于查询, 范围查询
InnoDB非主键索引怎么存储呢?
我们上面介绍的只是主键索引是这样存储的,那么非主键索引呢,其实非主键索引也B+树的,只有非主键索引的叶子节点存储的不是行记录数据,而是主键值,通过主键值再次索引获取所需要的数据。我画一个粗略的见图来表示
总结一下B+树索引
采用了多叉树的结构,降低了树的高度,减少了磁盘IO次数,通过对所有叶子节点通过指针双向链接,方便的提供了遍历所有数据的特性,同时数据也是严格有序的,方便范围查询,查询效率的稳定性也非常好。