思考并回答以下问题：
- 逻辑上相邻的记录在磁盘上也并不是一定物理相邻的。怎么理解？
- 什么是聚簇索引和非聚簇索引？
- InnoDB的数据文件本身就是索引文件是什么意思？
索引是什么？
MySQL官方对索引的定义为：索引是帮助MySQL高效获取数据的数据结构。
在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
索引的出现就是为了提高查询效率，就像书的目录。其实说白了，索引要解决的就是查询问题。
查询，是数据库所提供的一个重要功能，我们都想尽可能快的获取到目标数据，因此就需要优化数据库的查询算法，选择合适的查询模型来实现索引。
另外，为表设置索引要付出代价的：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间，因为索引也要随之变动。
常见查询模型
索引的实现模型有很多，这里我们先了解一下常用的查询模型。
顺序数组
顺序数组是一种特殊的数组，里面的元素，按一定的顺序排列。
顺序数组在查询上有着一定的优势，因为是有序的数据，采用二分查找的话，时间复杂度是O(log(N))。
顺序数组的优点就是查询效率非常高，但是要更新数据的话，就非常麻烦了。删除和插入元素都要涉及到大量元素位置的移动，成本很高。
因此，对于顺序数组更适合用于查询的领域，适合存储一些改动较小的静态存储引擎。
哈希索引
哈希表是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即key，就可以找到其对应的值即value。
哈希索引采用一定的哈希算法，对于每一行，存储引擎计算出了被索引字段的哈希码（Hash Code），把哈希码保存在索引中，并且保存了一个指向哈希表中的每一行的指针。
这样在检索时只需一次哈希算法即可立刻定位到相应的位置，速度非常快。
Hash索引结构的特殊性，其检索效率非常之高，应该是O(1)的时间复杂度。
虽然Hash索引效率高，但是Hash索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些：
1、Hash索引仅仅能满足=，IN和<=>查询，如果是范围查询检索，这时候哈希索引就毫无用武之地了。
因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索；
2、Hash索引无法利用索引完成排序，因为存放的时候是经过Hash计算过的，计算的Hash值和原始数据不一定相等，所以无法排序；
3、联合索引中，Hash索引不能利用部分索引键查询。
Hash索引在计算Hash值的时候是联合索引键合并后再一起计算Hash值，而不是单独计算Hash值。
所以对于联合索引中的多个列，Hash是要么全部使用，要么全部不使用。通过前面一个或几个索引键进行查询的时候，Hash索引也无法被利用。
4、Hash索引在任何时候都不能避免表扫描。
前面已经知道，Hash索引是将索引键通过Hash运算之后，将Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中，由于不同索引键可能存在相同Hash值，所以即使取满足某个Hash 键值的数据的记录条数，也无法从Hash索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
5、在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。
综上，哈希表这种结构适用于只有等值查询的场景，比如Memcached、redis及其他一些NoSQL引擎。
二叉搜索树索引
二叉搜索树的每个节点都只存储一个键值，并且左子树（如果有）所有节点的值都要小于根节点的值，右子树（如果有）所有节点的值都要大于根节点的值。
当二叉搜索树的所有非叶子节点的左右子树的节点数目均保持差不多时（平衡），这时树的搜索性能逼近二分查找；并且它比连续内存空间的二分查找更有优势的是，改变树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销。
特殊情况下，根节点的左右子树的高度相差不超过1时，这样的二叉树被称为平衡二叉树；与之相对的是，二叉搜索树有可能退化成线性树。
下图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。
为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。
B树
看得出来，二叉树在查询和修改上做到了一个平衡，都有着不错的效率，但是现实是很少有数据库引擎使用二叉树来实现索引，为什么呢？
数据库存储大多不适用二叉树，数据量较大时，树高会过高。
你可以想象一下一棵100万节点的平衡二叉树，树高20，每个叶子结点就是一个块，每个块包含两个数据，块之间通过链式方式链接。
树高20的话，就要遍历20个块才能得到目标数据，索引存储在磁盘时，这将是非常耗时的。
因此，为了减少磁盘的读取，查询时就要尽量少的遍历数据块，因此一般使用N叉树。
这里就有了B树（Balanced Tree）。
究竟什么是B树？
我们先看一个例子：
从上图你能轻易的看到，一个内结点x若含有n[x]个关键字，那么x将含有n[x]+1个子女。如含有 2个关键字D H的内结点有3个子女，而含有3个关键字Q T X的内结点有4个子女。
B树的特性
普及一些概念：
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 树的度：一棵树中，最大的节点的度称为树的度；
- 叶节点或终端节点：度为零的节点；
- 非终端节点或分支节点：度不为零的节点；
首先定义两个变量：d为大于1的一个正整数，称为B树的度。h为一个正整数，称为B树的高度。
B树是满足下列条件的数据结构：
1、每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
2、每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null。
3、除根结点和叶子结点外，其它每个结点至少有[ceil(m/2)]个孩子（其中ceil(x)是一个取上限的函数）；
4、所有叶节点具有相同的深度，等于树高h，且叶子结点不包含任何关键字信息。
5、key和指针互相间隔，节点两端是指针。
6、一个节点中的key从左到右非递减排列。
7、每个指针要么为null，要么指向另外一个节点。
8、每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。
其中：
- a) Ki(i=1…n)为关键字，且关键字按顺序升序排序K(i-1)<Ki。
- b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
- c) 关键字的个数n必须满足：[ceil(m / 2)-1]<= n <= m-1。
B树查找过程
由于B树的特性，在B树中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。
如上图所示，我们来模拟下查找文件29的过程：
1、根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作1次】
2、此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针p2；
3、根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作2次】
4、此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针p2；
5、根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作3次】；
6、此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。
分析上面的过程，发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。
B+树
B+树：是应文件系统所需而产生的一种B树的变形树。
一棵m阶的B+树和m阶的B树的异同点在于：
1、每个节点的指针上限为2d而不是2d+1。
2、所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。（B树的叶子节点并没有包括全部需要查找的信息）
3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字，不存储data。（B树的非终节点也包含需要查找的有效信息）
为什么说B+树比B树更适合做数据库索引？
1）B+树的磁盘读写代价更低
B+树的内部结点并没有存储关键字具体信息。因此其内部结点相对B树更小。
如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
2) B+树的查询效率更加稳定
由于非终端结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，进而每一个数据的查询效率相当。
几种树的对比
MySQL的索引模型
索引就是这种神奇伟大的存在。索引相当于数据库的表数据之外新建的数据结构，该数据结构的数据段中存储着字段的值以及指向实际数据记录的指针。
数据库表的索引从数据存储方式上可以分为聚簇索引和非聚簇索引（又叫二级索引）两种。
1、聚簇索引
表数据按照索引的顺序来存储的，也就是说索引项的顺序与表中记录的物理顺序一致。
对于聚簇索引，叶子结点即存储了真实的数据行，不再有另外单独的数据页。在一张表上最多只能创建一个聚集索引，因为真实数据的物理顺序只能有一种。
聚簇集是指实际的数据行和相关的键值都保存在一起。
注意：数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。
如果主键不是自增id，那么可以想象，它会干些什么，不断地调整数据的物理地址、分页。如果是自增的，那就简单了，它只需要一页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。
聚簇索引的二级索引：叶子节点不会保存引用的行的物理位置,而是保存了行的主键值
2、非聚集索引
表数据存储顺序与索引顺序无关。对于非聚集索引，叶结点包含索引字段值及指向数据页数据行的逻辑指针，其行数量与数据表行数据量一致。
聚簇索引是对磁盘上实际数据重新组织以按指定的一个或多个列的值排序的算法。特点是存储数据的顺序和索引顺序一致。一般情况下主键会默认创建聚簇索引，且一张表只允许存在一个聚簇索引。
这两个名字虽然都叫做索引，但这并不是一种单独的索引类型，而是一种数据存储方式。
下面，我们可以看一下MYSQL中MyISAM 和 InnoDB 两种引擎的索引结构。
MyISAM索引实现
MyISAM引擎使用B+树作为索引结构，叶节点的data域存放的是数据记录的地址，就是非聚集索引。
下图是MyISAM索引的原理图：
在MyISAM中，主键索引和辅助索引（Secondary key）在结构上没有任何区别，只是主键索引要求key是唯一的，而辅助索引的key可以重复。
InnoDB索引实现
虽然InnoDB也使用B+树作为索引结构，但具体实现方式却与MyISAM截然不同。
第一个重大区别是InnoDB的数据文件本身就是索引文件。
在InnoDB中，表数据文件本身就是按B+树组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
另外，第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。
对于聚簇索引存储来说，行数据和主键B+树存储在一起，辅助索引只存储辅助键和主键，主键和非主键B+树几乎是两种类型的树。
对于非聚簇索引存储来说，主键B+树在叶子节点存储指向真正数据行的指针，而非主键。
为了更形象说明这两种索引的区别，我们假想一个表如下图存储了4行数据。其中Id作为主索引，Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。
对于聚簇索引，若使用主键索引进行查询，where id = 14这样的条件查找主键，则按照B+树的检索算法即可查找到对应的叶节点，之后获得行数据。
若使用辅助索引进行查询，对Name列进行条件搜索，则需要两个步骤：
- 1、第一步在辅助索引B+树中检索Name，到达其叶子节点获取对应的主键。
- 2、第二步根据主键在主索引B+树种再执行一次B+树检索操作，最终到达叶子节点即可获取整行数据。这个过程称为回表。
聚簇索引的优势在哪？
1、由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键Id来组织数据，获得数据更快。
2、辅助索引使用主键作为指针而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作。
使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是InnoDB在移动行时无须更新辅助索引中的这个指针。
也就是说行的位置会随着数据库里数据的修改而发生变化，使用聚簇索引就可以保证不管这个主键B+树的节点如何变化，辅助索引树都不受影响。