MySQL索引
条评论MySQL索引
索引和事务是MySQL最重要的两个概念，而Innodb存储引擎的索引结构又是事务的基础，可谓重中之重。本文从二叉搜索树说起，直到B+树，详细解释MySQL索引的数据结构，试图从底层探究索引原理。
数据结构
基础
从查找说起，数据库查询就是查找的一种，不同的存储结构（数据结构）决定了查找的方法和效率。先从数据结构的角度看看为什么选用B树作为索引的数据结构。
二叉树
二叉树：每个节点最多有两个子节点。
节点的度：一个节点拥有的子树的个数。
满二叉树：除叶子节点外，其他节点都有两个子节点。满二叉树的最大特点是每一层次的结点数都达到最大值。
完全二叉树：只有最底层不满，最底层从左侧开始没有空的。
二分查找树
也叫二叉搜索树（BST树），首先是二叉树，其次每个节点上的值是有规律的：
- 左子树上所有结点的值均小于它的根结点的值；
- 右子树上所有结点的值均大于它的根结点的值。
查找的时候，从根节点开始比较，小于根的值就从左子树中递归查找，大于根的值就从右子树中递归查找。
添加节点也是一样，从根节点开始，递归找到合适的节点位置并添加。
删除节点麻烦一些，如果删除叶子节点比较简单，直接删除即可；如果删除非叶子节点，需要对数进行调整。
先序遍历二分查找树输出的结果就是排序结果。
下图为一颗二分查找树的例子。
AVL树
高度平衡二叉树，也叫平衡二叉树，在AVL树中任何节点的两个子树的高度最大差为一，这里不展开。
红黑树
前面提到的都是基础知识，在实战中使用的不多，常见的是由它们逐步引出的红黑树，JDK1.8中TreeMap和HashMap都用到了红黑树(Red Black Tree)。
从二叉树的发展来看，红黑树是一颗相对平衡的二叉树；二叉树–>二叉搜索树–>平衡搜索二叉树–> 红黑树；红黑树具有如下特点：
- 节点要么是黑色，要么是红色；
- 根和叶子节点都是黑色的；
- 不能有连续两个红色的节点；
- 从任一节点到它所能到达得叶子节点的所有简单路径都包含相同数目的黑色节点。
下图为一颗红黑树的例子，本文重点为了引出B+树，红黑树不展开。
为什么要引入红黑树？
二分查找树时间复杂度是O(log(n))，不是效率就已经够高了吗，直接使用不行吗？为什么还要发展到红黑树呢？因为二分查找树的运行时间取决于树的形状，树的高度越高，查询效率越低。试想最极端的情况，所有节点都只有右子树，那么查找最大的树需要遍历所有节点，相当于顺序查找。所以有了平衡的概念，越平衡的二分查找树效率越高。
想一下，二分查找树的高度就是最大的查询次数，所以树越高，效率越低。AVL树是高度平衡二叉树，红黑树是相对平衡二叉树，都是为了减小树的高度，提供查找效率。
以上可知，引入红黑树就是为了平衡。平衡的方法有三种：变色、左旋、右旋。
B树(B-tree)
B通常认为是Balance的简称，B树不是二叉树。一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。一颗M阶B树是一颗平衡的M路搜索树，它或者是空树，或者满足下列条件：
- 根结点至少有两个孩子；
- 每个中间节点都包含k-1个元素和k个孩子，其中 M/2 <= k <= M；(向上取整)
- 每个叶子节点都包含k-1个元素，其中 M/2 <= k <= M；(向上取整)
- 每个节点中的元素从小到大升序排列；节点当中k-1个元素正好是k个孩子包含的元素的值域划分；
- 所有的叶子节点都在同一层。
B树在插入时可能需要调整节点进行自平衡，删除也是一样；添加和删除节点后，可能导致不满足B+树条件，这个时候就需要调整，这个调整的过程称为自平衡。
我认为，二分查找树可以看作2阶的B树：每个节点都只有1个键值，2个子节点，左边子节点键值小于父节点键值，右边子节点键值大于父节点键值。以此类推，3阶的情况如下：每个节点有1-2个键值，1个键值的情况同上；如果有2个键值，那么有3个子节点。第N个子节点的键值位于父节点[N-1,N]键值之间。
以5阶B树为例，每个节点最多有4个元素，5个孩子。假设元素值为 (10, 20, 30, 40)，那么5个子节点的元素值范围是c0 <10，10 < c1 < 20，20 < c2 <30，30 < c3 < 40，c4 > 40 ，也就是分布于左右。
为什么引入B树？
我认为，B树是红黑树的升级版，更合适外部排序。换句话说，如果排序和查找都在内存中完成，那么红黑树就够用了，是很优秀的方案；如果排序和查找涉及到外部数据，也就是在磁盘上的数据，那么红黑树就不能满足要求了，所以引入了B树。B树在自平衡等很多算法上和红黑树是一样的，但是B树中一个节点可以保存更多的键值，一是减少了磁盘I/O，二是大大减小了树的高度。
B+树
B树有很多变种，B+树就是其中一种，MySQL使用B+树(实际上是B*树)作为索引的数据结构。
B+树与B树最重要的区别：
- B树所有节点都保存数据，B+树只有叶子节点保存数据；
B*树
基于B+树继续优化，增加顺序指针。
- 每个叶子节点增加一个指向相邻叶子节点的指针；这样可以提高区间查询的效率，例如：where age >= 30 and age < 50；
MySQL索引基础
索引分为聚簇索引和非聚簇索引两种，聚簇索引是按照数据存放的物理位置为顺序的，而非聚簇索引就不一样了；聚簇索引能提高多行检索的速度，而非聚簇索引对于单行的检索很快。
索引类型
- 按照索引数据和源数据是否分开存储，索引分为聚簇索引和非聚簇索引两种。
聚簇索引：索引数据和源数据存储在一起，或者说源数据就是按照主键作为索引组织的，Innodb存储引擎使用聚簇索引。
非聚簇索引：索引数据和源数据分开存储，MyISAM存储引擎使用非聚簇索引，数据文件有三个：.frm 文件存储表结构，.MYD 文件存储表数据，.MYI 文件存储索引数据。
- 按照使用类型，索引可以分为普通索引、唯一索引、全文索引和复合索引
普通索引
CREATE INDEX index_name ON table_name(column(length)); |
唯一索引
与普通索引类似，不同的是索引列的值必须唯一，但允许有空值（注意和主键不同）。
CREATE UNIQUE INDEX indexName ON table_name(column(length)); |
全文索引
FULLTEXT索引只适用于 MyISAM，一般不用。
复合索引
顾名思义，复合索引是由2个或者更多字段组合而成的索引。普通索引和唯一索引都是单字段的。
CREATE INDEX index_name ON table_name(column1(length1), column2(length2)); |
注意，复合索引遵循最左前缀原则，上面的SQL实际上建立了column1和column1+column2两个索引。
最左前缀原则，就是从最左侧开始组合，如果创建了column1、column2、column3复合索引，那么实际上已经有了如下三个索引，无需在单独在column1上建索引，但是column2和column3是没有索引的：
- column1
- column1+column2
- column1+column2+column3
- 安装数据结构，索引可以分为BTREE索引和HASH索引
BTREE索引，就是使用B+/B*树存储索引，前面说过。
HASH索引，
MySQL索引原理
MySQL索引使用改进的B+树来实现。
为什么用B+树存储索引
为什么不使用二分查找树来实现索引呢？二分查找树效率也很高啊，时间复杂度O(log(n))。
如果索引全部在内存中，那么使用二分查找树是没有问题的。但实际情况中，索引文件可能很大，不可能全部加载到内存中，这就意味着对索引的访问涉及到磁盘I/O。也就是说，虽然二分查找树算法的比较次数少，但是需要去和磁盘上的索引数据进行比较，访问太慢，虽然次数少，但是时间长。
简单分析一下磁盘I/O，磁盘由磁片和磁头组成，磁片旋转
那么，B+树难道就不需要访问磁盘I/O了，内存同样放不下啊。实际操作中，我们每次加载磁盘一页的数据到内存中，MySQL索引B+树的每一个节点就保存一页数据，可以一次加载到内存中。这样，虽然比较次数多了，但是磁盘I/O次数少了，整体还是高效的。
二分查找树（二叉搜索树）本质上是二叉树，当数据量比较大时，树的高度一定非常高。B+树是多路搜索树，当阶数比较大时，树的高度可以很低。如果索引数据需要从磁盘加载，那么树的高度就决定了磁盘I/O的次数，也就决定了执行速度。
以查找数据10为例，二分查找树需要4次比较和4次磁盘I/O；
MyISAM实现
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。MyISAM的索引方式也叫做“非聚簇索引”。
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。
InnoDB实现
虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。所以，表必须要有主键。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
B+Tree 中的B是指 balance ，意为平衡。需要注意的是，B+树索引并不能找到一个给定键值的具体行，它找到的只是被查找数据行所在的页，接着数据库会把页读入到内存，再在内存中进行查找，最后得到要查找的数据。
MySQL索引使用
高效使用索引的首要条件是知道什么样的查询会使用到索引，这个问题和B+Tree中的“最左前缀原理”有关，下面通过例子说明最左前缀原理。
复合索引
索引失效
索引命中
<，<=，=，>，>=，BETWEEN，IN, like 'xx%'
索引不能命中
<>，not in ，!=，like '%xx'
1.索引不存储null值
更准确的说，单列索引不存储null值，复合索引不存储全为null的值。索引不能存储Null，所以对这列采用is null条件时，因为索引上根本
没Null值，不能利用到索引，只能全表扫描。
为什么索引列不能存Null值？
将索引列值进行建树，其中必然涉及到诸多的比较操作。Null值的特殊性就在于参与的运算大多取值为null。
这样的话，null值实际上是不能参与进建索引的过程。也就是说，null值不会像其他取值一样出现在索引树的叶子节点上。
2.不适合键值较少的列（重复数据较多的列）
假如索引列TYPE有5个键值，如果有1万条数据，那么 WHERE TYPE = 1将访问表中的2000个数据块。
再加上访问索引块，一共要访问大于200个的数据块。
如果全表扫描，假设10条数据一个数据块，那么只需访问1000个数据块，既然全表扫描访问的数据块
少一些，肯定就不会利用索引了。
3.前导模糊查询不能利用索引(like ‘%XX’或者like ‘%XX%’)
假如有这样一列code的值为’AAA’,’AAB’,’BAA’,’BAB’ ,如果where code like ‘%AB’条件，由于前面是
模糊的，所以不能利用索引的顺序，必须一个个去找，看是否满足条件。这样会导致全索引扫描或者全表扫
描。如果是这样的条件where code like ‘A % ‘，就可以查找CODE中A开头的CODE的位置，当碰到B开头的
数据时，就可以停止查找了，因为后面的数据一定不满足要求。这样就可以利用索引了。
4.索引失效的几种情况
1.如果条件中有or，即使其中有条件带索引也不会使用(这也是为什么尽量少用or的原因)
要想使用or，又想让索引生效，只能将or条件中的每个列都加上索引
2.对于多列索引，不是使用的第一部分，则不会使用索引
3.like查询以%开头
4.如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引
5.如果mysql估计使用全表扫描要比使用索引快,则不使用索引
5.MySQL主要提供2种方式的索引：B-Tree索引，Hash索引
B树索引具有范围查找和前缀查找的能力，对于有N节点的B树，检索一条记录的复杂度为O(LogN)。相当于二分查找。
哈希索引只能做等于查找，但是无论多大的Hash表，查找复杂度都是O(1)。
显然，如果值的差异性大，并且以等值查找（=、 <、>、in）为主，Hash索引是更高效的选择，它有O(1)的查找复杂度。
如果值的差异性相对较差，并且以范围查找为主，B树是更好的选择，它支持范围查找。
Innodb插入优化
InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。
如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。
如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
只要可以，请尽量在InnoDB上采用自增字段做主键。