索引是什么
将字段（数据）按照一定顺序排列，从而提高检索速度，其效果就像书的目录一样，你要找什么内容，先检索目录，获取到内容位置，然后跳转到对应位置读取数据。
索引的常见模型
哈希表、有序数组和搜索树
哈希表：采用键值对的方式来组织数据，底层采用数据存储，检索数据时，基于输入的查找内容进行hash计算，映射到数据中的对应位置，从而实现了数据快速查找。
优点：能够实现O(1)时间复杂度的查找
缺点：因为查找前需要进行hash计算，有一点点的性能损失；更重要的是，不支持快速的
有序数组：采用数组的方式来存储数据。
优点：能够快速的按范围查找数据。
缺点：在数组中插入数据，维护成本大，需要搬移插入点之后的数据。
二叉搜索树：搜索树中的任意节点大于其左子树的节点值，小于其右子树的节点值。
优点：能够实现快速的按范围查找数据，能够支持到 O(logN) 的查询时间复杂度，
缺点：为了维持 O(log(N)) 的查询复杂度，需要保证数的平衡，常见的平衡树VAL，但是应用并不是很广泛，相比红黑树，红黑树是相对平衡的二叉搜索树，红黑树应用比VAL广泛是因为其维护成本比VAL低，也就是说红黑树在查询性能和平衡处理的两点上做到了相对平衡。
MYSQL中InnoDB 的索引采用的是多叉树，而不是二叉树，原因很简单二叉树只有两个节点能存储数据，多叉树则有大于2的n个节点存储数据。
多叉树相比二叉树，相同数量的节点，多叉树的高度就比二叉树矮，对应到机械硬盘寻址时，就会减少寻址次数。
B+树
MYSQL中InnoDB 的索引使用的就是n叉树，叫做B+树。
索引组织表
MYSQL中InnoDB中的表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。
聚簇索引
MYSQL中InnoDB中表的主键，都是包含正行的全部数据，这种索引也叫做聚簇索引，一张表只能有一个聚簇索引。
其余普通索引，索引中存储的都是主键索引的值。