为什么选择B+树作为索引结构 b树索引和b+树索引的区别
从前面讲的InnoDB数据页结构，特别是页目录，我们可以了解到，记录在页里面是以单链表的形式存在，而页与页之间构成了双向链表 。
文章插图
那么我们应该采取什么样的方式来更高效查询数据呢？
# 1.我们先来假设不了解什么是索引，我们会怎么查找？
比如根据主键条件搜索，可以再页目录中用二分查找查到属于那条记录
如果是非主键列呢，因为在数据页中并没有对非主键列建立所谓的
页目录，可能要一个一个按顺序找，知道找到匹配的记录# 2.如果在很多页中查找？
大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录 。在很多页中查找记录的话可以分为两个步骤：
- 定位到记录所在的页 。
- 从所在的页内中查找相应的记录 。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录 。因为要遍历所有的数据页，所以这种方式显然是超级耗时的，如果一个表有一亿条记录，使用这种方式去查找记录那要等到猴年马月才能等到查找结果 。所以祖国和人民都在期盼一种能高效完成搜索的方法，索引同志就要亮相登台了 。
# B+树索引
我们现在就遇到了个难题，在一个数据页里面根据主键查询记录，可以很快的查询出来，但是数据库的数据会越来越多，数据页也会越来越多，页与页之间现在没有办法根据主键查到记录属于哪个页？
要是能像一个数据页里面根据二分法查记录就好，咦！没错，就是这个思路！
设计InnoDB的大叔，给多个数据页分配了各自的目录，方便查找到某个数据页，比如下面
文章插图
就像一本字典，大部分装着对单词的解释（数据页），前面一部分是目录（存放目录项记录的数据页），都占据着书本的空间，但是起到方便查找的作用
从图中可以看出来，我们新分配了一个编号为 30 的页来专门存储 目录项记录。这里再次强调一遍
目录项记录和普通的 用户记录 的不同点：- 目录项记录 的 record_type 值是1，而普通用户记录的 record_type 值是0 。
- 目录项记录 只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有 InnoDB 自己添加的隐藏列 。
- 还记得我们之前在唠叨记录头信息的时候说过一个叫 min_rec_mask 的属性么，只有在存储 目录项记录 的页中的主键值最小的 目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0。
除了上述几点外，这两者就没啥差别了，它们用的是一样的数据页（页面类型都是 0x45BF ，这个属性在 File Header 中，忘了的话可以翻到前边的文章看），页的组成结构也是一样一样的（就是我们前边介绍过的7个部分），都会为主键值生成
Page Directory （页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度 。现在以查找主键为 20的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：
