页

mysql中的页和操作系统的页有点类似，都是逻辑单位。都是假设数据在磁盘上是一起的，我们读取磁盘的时候一次读一页，而不是一条一条的数据来取，一页上可能会有多条数据，再取后面的数据的时候就先去已读取的页中查看，提高效率。操作系统的页是4KB，mysql的页默认是16KB。

innodb数据页结构及其中的目录

每条记录中有个next_record字段，这玩意儿非常重要，它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量，所以数据页每条记录是个单向链表。

既然是单向链表，如果页里数据比较多，用遍历效率是不高的。所以我们在数据页里再做个目录。

怎么做目录？分槽。 把16k数据分成若干槽，每个槽里面有若干条记录。由于记录都是主键递增的，每个槽都取的最后一条的偏移量，那么槽也是递增的。查找的时候先对槽进行二分查找，再对槽里面的数据进行遍历。

索引实现

不同的存储引擎采用不同的实现方式。

MyISAM 非聚集索引

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。

我们看到，索引文件本身和数据表的文件是分离的，这也是非聚集索引的由来。叶子节点的data区域存放的是数据表每条记录的地址。

其实叶子节点都是页，里面又很多数据，当页数据满的时候在加一个页。

InnoDB聚集索引

InnoDB的主键索引也使用B+Tree作为索引结构，但这里表数据文件本身就是B+树的一个结构，也就是说叶子节点的data区域保存了完整的数据表的一条记录。索引的key就是表的主键，这就是聚集索引的由来。

由此看来，InnoDB的数据表必须要有一个主键，如果没有指定，mysql就会自动选择一个唯一标识记录的作为主键。那这样的也不存在怎么办？mysql就会生成一个隐含的6字节长整型作为主键。

现在看下如何定位一个Record：

1 通过根节点开始遍历一个索引的B+树，通过各层非叶子节点最终到达一个Page，这个Page里存放的都是叶子节点。

2 在Page内从”Infimum”节点开始遍历单链表（这种遍历往往会被优化），如果找到该键则成功返回。如果记录到达了”supremum”，说明当前Page里没有合适的键，这时要借助Page的Next Page指针，跳转到下一个Page继续从”Infimum”开始逐个查找。

B+树本身就是一个目录，或者说本身就是一个索引。 它有两个特点:

1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义: 页内的记录是按照主键的大小顺序排成一个单向链表。 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
2. B+树的叶子节点存储的是完整的用户记录。 所谓完整的用户记录，就是指这个记录中存储了所有列的值(包括隐藏列)。

InnoDB的次级索引

InnoDB还有个地方与MyISAM不同，就是辅助索引data记录的是主键的值而不是数据表记录的地址。此时，索引文件和数据文件是分开的。

这样就要注意了，InnoDB主键不要太大，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。

当通过辅助索引来寻找数据时，Innodb存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。这种在二级索引中不能找到所有需要的数据列的现象，被称为非覆盖索引，反之称为覆盖索引。

这个B+树与上边介绍的聚簇索引有几处不同: 使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义: 页内的记录是按照c2列的大小顺序排成一个单向链表。 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。 B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。 目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。

采用B+树的原因

B+树的特点决定的。查询一般为log(n)。选择B+树而不是其他数据结构的原因主要是因为数据是保存在硬盘上而不是内存中，所以减少磁盘IO次数才是提升效率的关键。

1. B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2. B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3. 由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

总结： Hash索引查询是O(1),应该是更快，但是为啥不用呢？因为大多数情况下并不是每次只查询一个，而是多个，比如前10条，b+树叶子节点有链接，所以能快速查询。另外，文件或数据库索引数据比较大，也不做不到一次加载到内存，但是B树可以一个一个节点的加载，进行查询。