mysql索引为什么选择B+树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了mysql索引为什么选择B+树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2697字，纯文字阅读大概需要4分钟。

内容图文

mysql索引的出现是为了提高查询效率，可以提高读写效率的数据结构有很多种，这里介绍几种：哈希表、数组、B树以及B+树。

1、哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。

假如维护着一张身份证信息和姓名表，需要根据身份证号查询姓名，这时哈希索引如下图：

图中，User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将 ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。

需要注意的是，图中4个ID_card_n的值不是递增的，这样做的好处是新增的时候很快，往后追加即可；缺点是因为不是有序的，所以做区间查询很慢，查询[id_card_nx,id_card_ny]之间的用户，就必须全部扫描一遍了。所以哈希结构适合做等值查询，比如 Memcached 及其他一些 NoSQL 引擎。
2、有序数组：有序数组在做等值查询和区间查询效率都是很高的，假设我们用有序数组实现上图的身份证查姓名的例子，如下图：

假设身份证号没有重复，这个数组就是按照身份证号递增的顺序排序的。此时如果需要查询ID_card_n2对应的姓名，通过二分法就可以快速查到，时间复杂度为O(log(N))。
同时，这个索引结构是支持区间查询的。如果要查询[ID_card_X,ID_card_Y]之间的User,可先通过二分法查到ID_card_X,然后向右遍历，直到第一个大于ID_card_Y的User，然后退出循环。
如果只看查询效率，有序数组就是最好的索引结构了，但是插入数据的时候，效率会很低，因为为了维护连续性和有序性，后面所有的元素必须挪动，代价很大。

B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。
1、根节点至少有两个子节点；
2、每个节点有M-1个key，并且以升序排列；
3、位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间；
4、其它节点至少有M/2个子节点。
B+树是B树的一种变形，区别在于：
1、有k个子结点的结点必然有k个关键码；
2、非叶结点仅具有索引作用，跟记录有关的信息均存放在子叶结点中。
3、树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
B和B+树的区别在于，B+树非叶子节点只包含key信息，不存储实际的值，所有的叶子节点和相邻的节点使用链表相连，便于区间查询。
B+ 树的优点在于：
由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

综上所述，可得出Innodb为什么选择B+树做索引的结构。

参考资料：

B树和B+树参考：https://www.cnblogs.com/vincently/p/4526560.html
极客时间《mysql45讲》：深入浅出索引上

内容总结

以上是互联网集市为您收集整理的mysql索引为什么选择B+树全部内容，希望文章能够帮你解决mysql索引为什么选择B+树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端