文章目录

• 前言
• 1.Mysql为啥使用B+树：
• 1.1 hash表和二叉树、红黑树、AVL树：
• 1.2 B树和B+树：
• 2.一棵B+树能存多少数据：
• 总结

前言

Mysql现在是大多数互联网公司的首选关系型数据库，很多开发人员经常用，但是可能面试的时候问到为啥使用B+索引，和一棵树能存放多少数据问题的时候不太能答上来，本篇来进行个通俗易懂的普及，希望能帮助到使用mysql的程序员员们。

1.Mysql为啥使用B+树：

像上面说的，mysql使用的很广泛，所以其性能很重要，底层的存储引擎和数据检索引擎就显的比较重要。

1.1 hash表和二叉树、红黑树、AVL树：

• 散列算法查询某个具体的key地址查询数据很快，时间复杂度o(1)，但是查询范围数据的时候hash的速度就不行，所以hash不适合做底层mysql的底层索引数据结构。
• 普通的二叉树因为有从左到右依次升序的特征，查询的复杂度为O(logn)，相对于hash索引，支持范围的有效查询，但是极端情况下的二叉树会变成线性链表，就导致查询复杂度变成O(N)，所以二叉树也不能作为mysql的底层数据索引结构。
• 红黑树是一种弱的平衡二叉树，通过左旋右旋保持基本的平衡状态，拥有不错的平均查找效率，不会存在O(N)的情况，但是红黑树存在右倾的可能性，数据量大的时候，右倾的查找效率也会很低，所以也不考虑。
• AVL是一种绝对平衡的二叉树，不会有红黑树的右倾缺点，可以实现范围查找，数据排序。但是AVL的缺点是每个节点只存放一个数据，如果使用AVL树作为myql底层索引数据结构的话，磁盘IO的次数会很多，效率仍然很低。磁盘IO的特点是读取1b的数据和读取1kb的数据消耗时间一致，根据这个特点，后面有了B树和B+树。

1.2 B树和B+树：

• B树相对于AVL平衡二叉树，每个节点存放了很多数据，减少了磁盘IO的次数，支持范围查找，时间复杂度：h*logN，就是树高和节点的数量。但是B树的缺点是节点存放数据，造成树高会很高在大量数据的情况下。
• B+树相对B树，非叶子节点存储的是索引和指针，能够存储很多，只有叶子节点存放的是数据，这样就保证了树的高度不高，减少磁盘的IO次数，在加上叶子节点是链表链接起来的，这样查找效率就提升上来了。所以B+树作为Myql的底层的索引数据结构非常的合理。

2.一棵B+树能存多少数据：

针对InnoDB引擎来说，一个节点页大小为16KB，上面说的叶子节点只存放数据，那么一页存放1kb的一行数据（基本上一行就是1kb左右），为16。非叶子节点存放的是索引和指针，索引大小按照bigint8字节计算，指针是6字节，总共14b。那么非叶子节点一页存放的数据就是161024/14约1170个，如果树高是2层的话：117016约18724条数据。
如果三层树高的话：1170117016约2千万的数据而每次查询只需要查3次，这样的结果让B+树完美胜出Mysql的底层数据索引结构。

总结

上面也是我参考很多的文章形成自己的总结性的语言给大家进行介绍Mysql使用B+树和B+树存放数据的介绍，总的感觉来说讲的比较的通俗易懂，理解起来应该比较容易，希望能帮助到正在使用Mysql的朋友们，欢迎关注公众号：Java时间屋 进行留言交流。