索引（Index）是帮助 MySQL 高效获取数据的数据结构。常见的查询算法
顺序查找
二分查找
二叉排序树查找
哈希散列法
分块查找
平衡多路搜索树B树（B-tree）

索引原则

1. 选择唯一性索引：唯一性索引的值是唯一的，可以更快速的通过该索引来确定某条记录
2. 为经常需要排序、分组和联合操作的字段建立索引
3. 为常作为查询条件的字段建立索引
4. 限制索引的数目：越多的索引，会使更新表变得很浪费时间。尽量使用数据量少的索引
5. 如果索引的值很长，那么查询的速度会受到影响。尽量使用前缀来索引
6. 删除不再使用或者很少使用的索引
7. 最左前缀匹配原则，非常重要的原则
8. 尽量选择区分度高的列作为索引：区分度的公式是表示字段不重复的比例
9. 索引列不能参与计算，保持列“干净”：带函数的查询不参与索引
10. 尽量的扩展索引，不要新建索引。

为什么要使用索引？

为了避免全表扫描情况的发生，快速查询数据。
为了提高查询效率，就像书的目录。其实说白了，索引要解决的就是查询问题。

什么样的信息能称为索引

主键、唯一键以及普通键等

优化索引

1. 二叉搜索树
二叉搜索树的每个节点都只存储一个键值，并且左子树（如果有）所有节点的值都要小于根节点的值，右子树（如果有）所有节点的值都要大于根节点的值。
当二叉搜索树的所有非叶子节点的左右子树的节点数目均保持差不多时（平衡），这时树的搜索性能逼近二分查找；并且它比连续内存空间的二分查找更有优势的是，改变树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销。
特殊情况下，根节点的左右子树的高度相差不超过 1 时，这样的二叉树被称为平衡二叉树；与之相对的是，二叉搜索树有可能退化成线性树。

数据库存储大多不适用二叉树，数据量较大时，树高会过高。

2. B树 (Balanced Tree)

从上图你能轻易的看到，一个内结点 x 若含有 n[x] 个关键字，那么 x 将含有 n[x]+1 个子女。如含有 2 个关键字 D H 的内结点有 3 个子女，而含有 3 个关键字 Q T X 的内结点有 4 个子女。

首先定义两个变量：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 树中按 key 检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的 data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到 null 指针，前者查找成功，后者查找失败。

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

4. 运用Hash
哈希表是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即key，就可以找到其对应的值即value。
哈希索引采用一定的哈希算法，对于每一行，存储引擎计算出了被索引字段的哈希码（Hash Code），把哈希码保存在索引中，并且保存了一个指向哈希表中的每一行的指针。
这样在检索时只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

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. 由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键 Id 来组织数据，获得数据更快。
2. 辅助索引使用主键作为指针而不是使用地址值作为指针的好处是，**减少了当出现行移动或者数据页分裂时辅助索引的维护工作。**使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是 InnoDB 在移动行时无须更新辅助索引中的这个指针。也就是说行的位置会随着数据库里数据的修改而发生变化，使用聚簇索引就可以保证不管这个主键 B+ 树的节点如何变化，辅助索引树都不受影响。

稀疏索引：叶子节点仅保存了键位信息以及该行数据的地址，有的稀疏索引只保存了键位信息机器主键。叶结点包含索引字段值及指向数据页数据行的逻辑指针
这两个名字虽然都叫做索引，但这并不是一种单独的索引类型，而是一种数据存储方式。

myisam存储引擎：不管是主键索引，唯一键索引还是普通索引都是稀疏索引
MyISAM 引擎使用 B+ 树作为索引结构，叶节点的 data 域存放的是数据记录的地址，就是非聚集索引。

下图是MyISAM索引的原理图

innodb存储引擎：有且只有一个密集索引。

密集索引的选取规则如下：
若主键被定义，则主键作为密集索引
如果没有主键被定义，该表的第一个唯一非空索引则作为密集索引
若不满足以上条件，innodb内部会生成一个隐藏主键（密集索引）
非主键索引存储相关键位和其对应的主键值，包含两次查找
虽然 InnoDB 也使用 B+ 树作为索引结构，但具体实现方式却与 MyISAM 截然不同。第一个重大区别是 InnoDB 的数据文件本身就是索引文件。
第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。

为了更形象说明这两种索引的区别，我们假想一个表如下图存储了 4 行数据。其中Id作为主索引，Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。

索引最左匹配原则

CREATE TABLE `user2` (
  `userid` int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) NOT NULL DEFAULT '',
  `password` varchar(20) NOT NULL DEFAULT '',
  `usertype` varchar(20) NOT NULL DEFAULT '',
  PRIMARY KEY (`userid`),
  KEY `a_b_c_index` (`username`,`password`,`usertype`)
) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8;

上表中有一个联合索引，下面开始验证最左匹配原则。
当存在username时会使用索引查询：

explain select * from user2 where username = '1' and password = '1';

没有username时，不会使用索引查询：

explain select * from user2 where password = '1';

当有username，但顺序乱序时也可以使用索引：

explain select * from user2 where password = '1' and username = '1';

索引是建立得越多越好吗

数据量小的表不需要建立索引，因为建立索引会增加额外的开销。
数据变更需要维护索引，因此更多的索引意味着更多的维护成本。
更多的索引意味着更多的存储空间。