93.Mysql为啥使用B+索引，一棵B+树能存多少数据？

前言

1.Mysql为啥使用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的底层数据索引结构。