mysql索引的数据结构,为什么用B+树不用B树 mysqlb+树索引( 二 ) _生活百科

但是如果你不是通过主键去查询的，槽位此时就排不上用场，你还得一个一个遍历数据页中的单向链表去找到你想要的那行数据。
2.2 索引的前夕-页分裂
这里我们先来个小插曲，简单了解下页分裂，这块内容也是后面索引机制能够正常运行的基础。
我们都知道一个数据页就是16KB大小，当一个数据页中的数据行足够多时就会重新创建一个数据页继续写数据行，如果说我们没有用到索引还好，但是如果我们要在表中创建索引，那么对多个数据页中的数据就有约束了。
如果新创建的数据页中的数据行的主键值，存在比它上一个数据页的主键值还小的情况，这种情况是不被允许的，如下图所示：

文章插图
如果出现上图的情况，多个数据页之间的主键就无序了，而索引机制的实现是要基于多个数据页主键的大小是依次递增的，所以此时就会出现页分裂的情况。
其实页分裂目的也很明确，就是调整下不同数据页的数据顺序，使得最终按顺序创建的索引页之间，后一个数据页中的每一个数据行的主键值都要大于上一个数据页，当然一个数据页中当然是按照单向链表的方式依次递增的，页分裂流程如下图所示：

文章插图
我们可以看到页分裂主要就是调整了下数据页之间数据行的数据的顺序，使得多个数据页之间的主键值是按照顺序来存放的，在这样有序的数据中，高效查询才变得可能。
频繁的出现页分裂情况，毕竟页分裂要涉及到数据的移动，在性能上也是会有损耗的，这也警示我们减少页分裂的出现概率是非常有必要的，在设计表结构时我们可以尽量使用主键自增长的方式，而不是用很难保证主键顺序的自定义创建主键的方式，使用主键自增长方式，能大大避免说数据页之间主键大小出现顺序错乱的问题，减少页分裂发生的概率。
2.2 从主键目录到索引页
查询一行数据，在物理层面就是定位到哪一个数据页中的哪一行数据。在数据页中定位数据的问题，在之前我们已经通过槽位的方式优化了查询的效率，现在我们要解决的是如何在大量的数据页中定位数据页，这就是索引的目标。
（1）主键目录

InnoDB存储引擎一开始是使用主键目录的方式，将数据页号和数据页最小的主键值作为一条记录，如下图所示：

文章插图
这样的话，我们要查哪一条数据就不用扫描一个数据页内的所有数据再扫描下一个了，直接通过id去主键目录看一下，通过二分查找定位到具体哪个数据页，然后数据页内部通过定位槽位，遍历那个槽位对应数据行分组找到具体的一行数据。
（2）索引页

现在有一个问题就是，每张表对应的数据页都有很多，主键目录就会有大量的数据、就有可能放不下，这时InnoDB设计者们就想存放目录数据也是数据啊，为什么不可以使用数据页来放呢，就这样主键目录的信息就被移到数据页来了，而这些数据页就被称为索引页，如下图所示：

文章插图
从这里我们可以知道数据页肯定不是简单只存放数据表中的数据的。好了，现在主键目录由于容量有限，我们把主键目录信息移动到了数据页中形成了索引页，但同样的问题不还是会出现吗，一个数据页的大小也才16KB，索引页本身的容量也是有限的，容量不够了该怎么办呢？
为了解决索引页容量不够的问题，索引页会重新创建和升级，先把超出容量的数据放到一个新的索引页中，然后再加一层索引页，如下图所示：

文章插图
由上图我们可以看到，新的一层索引页35它存放的就不是最小主键对应的数据页目录了，而是最小主键对应的索引页目录了，以此类推如果索引页35这里容量也不够呢，那就继续往上一层扩展啊，最终效果看起来就像下面一样：

文章插图
大家看出来了吗，由索引页一层一层组成的结构不就是我们经常说的索引树吗，而这棵树在mysql中称之为B+索引树。
树这种数据结构天然可以使用二分法查询，所以现在如果我们要查询一条数据，从树的根节点开始通过二分法查找，以O(logn)的时间复杂度锁定数据页，然后在数据页中同样使用二分法锁定槽位，在槽位中简单遍历下不就找到数据了吗，相比于没有索引的场景，速度那可是相当快了。