一分钟掌握MySQL的InnoDB引擎B+树索引

内容导读

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

内容图文

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次数，通过对所有叶子节点通过指针双向链接，方便的提供了遍历所有数据的特性，同时数据也是严格有序的，方便范围查询,查询效率的稳定性也非常好。

一分钟掌握MySQL的InnoDB引擎B+树索引

标签：ceil   相对   才有   mys   索引   基础   ima   code   nod   

本文系统来源：https://www.cnblogs.com/sy270321/p/12904825.html

内容总结

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

内容备注

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

内容手机端