JAVA索引机制探寻

索引：
一、什么是索引
MySQL官方对于索引的定义为：索引是帮助MySQL高效获取数据的数据结构。
数据库查询是数据库最主要的功能之一，我们都希望查询数据的速度尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找，当然这种时间复杂度为O(N)的算法在数据量很大时显然是糟糕的，于是有了二分查找O(log N)、二叉树查找等。但是二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树，但是数据本身的组织结构不可能完全满足各种数据结构。所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
插曲：大O表示法。检查长度为n的列表，二分查找最坏的情况需要执行log N次操作，使用大O表示法来表示算法的运行时间，也就是O(log N)。括号里面指算法需要执行的操作次数。
二、优势
　　类似大学图书馆建书目索引，提高数据检索效率，降低数据库的IO成本。
通过索引对数据进行排序，降低数据排序的成本，降低了CPU的消耗。
三、劣势
　　实际上索引也是一张表，该表保存了主键与索引字段，并指向实体表的记录，所以索引列也是要占空间的。
　　虽然索引大大提高了查询速度，同时确会降低更新表的速度，如对表进行INSERT、UPDATE、DELETE。
因为更新表时，MySQL不仅要保存数据，还要保存一下索引文件每次更新添加了索引列的字段。
四、数据结构
1、二叉树

从算法逻辑上，二叉树的查找速度和比较次数都是很小的，但是数据库索引必须考虑一个问题：磁盘IO。
索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数。
当数据量很大的时候，索引文件也很大，无法一次性加载整个索引到内存，只能逐一加载每一个磁盘页（磁盘的储存单位）。

磁盘预读和局部性原理

从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址。
由于磁盘存取速度很低，为了提高效率，磁盘一般都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。
局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块。

如上图二叉树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性；

很明显，二叉树的磁盘IO次数跟二叉树的深度有关，由于每个节点存储的元素数量有限，所以二叉树的深度h比较大，IO读写过于频繁，所以有了所谓的B树（多路平衡查找树）。

而B-TREE利用了磁盘预读，将一个节点的大小设为等于一个磁盘页，这样每个节点只需要一次I/O就可以完全载入。

2、B-树
一个 m 阶的B树满足以下条件：
a、每个结点至多拥有m棵子树；
b、根结点至少拥有两颗子树（存在子树的情况下）；
d、除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树；
d、所有的叶结点都在同一层上；
e、有 k 棵子树的分支结点则存在 k-1 个关键码，关键码按照递增次序进行排列；
f、关键字数量需要满足ceil(m/2)-1 <= n <= m-1；

第一次磁盘IO：

在内存中定位（和9比较）：

第二次磁盘IO：

在内存中定位（和2，6比较）：

第3次磁盘IO：

在内存中定位（和3，5比较）：

与二叉树相比：
查询次数并不比二叉树少，尤其单一节点元素数量很多；
但是跟磁盘IO的速度比，内存比较基本可以忽略，B-树相对高度更低，IO次数少，查询性能就会高。

复杂度：度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN).

对高度为h的m阶B树进行操作：
插入
A、如果该结点的关键字个数没有到达m-1个，那么直接插入即可；
B、如果该结点的关键字个数已经到达了m-1个，那么根据B树的性质显然无法满足，需要将其进行分裂。
分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。

删除
A、如果该结点拥有关键字数量仍然满足B树性质，则不做任何处理；
B、如果该结点在删除关键字以后不满足B树的性质（关键字没有到达ceil(m/2)-1的数量），则需要向兄弟结点借关键字，这有分为兄弟结点的关键字数量是否足够的情况。
如果兄弟结点的关键字足够借给该结点，则过程为将父亲结点的关键字下移，兄弟结点的关键字上移；
如果兄弟结点的关键字在借出去以后也无法满足情况，即之前兄弟结点的关键字的数量为ceil(m/2)-1，借的一方的关键字数量为ceil(m/2)-2的情况，那么我们可以将该结点合并到兄弟结点中，合并之后的子结点数量少了一个，则需要将父亲结点的关键字下放，如果父亲结点不满足性质，则向上回溯；

3、B+树
A、所有的叶子结点中包含了全部元素信息，及指向这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
B、所有的中间节点元素都同时存在于子节点，是最大（小）元素。

如上图，叶子节点包含了全量信息，每个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。
卫星数据：指的是索引元素所指向的数据记录，比如指向数据库的某一行(下图中的data)。
B-树中，无论中间节点还是叶子节点都带有卫星数据（如下图）。

B+树中，只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联（如下图）。

注意：在数据库的聚集索引中，叶子节点直接包含卫星数据。在非聚集索引中，叶子节点带有指向卫星数据的指针。

比较范围查找：如查询3-11：
B-树：

B+树：找到范围的下限（3）后，直接通过链表指针即可。

**B+树的优势：
1.单一节点存储更多的元素（因为不包含卫星数据），使得查询的IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。
3.所有叶子节点形成有序链表，便于范围查询。**
索引对增删改的操作性能影响大：
把数据插入索引的过程中，为了维护索引中字段的顺序，会先在索引中查找这个值，如果能找到，就把这个值查到后面空闲的地方，如果没有找到，就先把值加入到叶子节点，然后在分支节点中新增这个值 和 指向叶子节点的指针（就是一个地址）。
在这个过程中，如果某个页满了，还要新申请一个空的页，把满的页拆分开，把一半的索引数据放到空闲页中，而且为了保证数据的一致性（这个插入操作是并发的，可能有几十上百个线程同时进行），会给相关的索引页加上闩锁（一种更低级别的内存锁）。这个过程的开销是很大的。
五、mysql的MyISAM和InnoDB两个存储引擎的索引
MyISAM索引的B+树实现：
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。

如下图，设表一共有三列，假设我们以Col1为主键，是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

InnoDB索引实现：
1、InnoDB的数据文件本身就是索引文件。在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
如下图：叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有）。

2、InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。如下图为定义在Col3上的一个辅助索引：

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
Q：InnoDB为什么不建议使用过长的字段作为主键？
A：因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。
Q：用非单调的字段作为主键在InnoDB中好不好？
A：因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
六、索引的高性能策略
创建索引：CREATE INDEX idx_fis_outin_store_union ON fis_outin_store(company_id,warehouse_id,err_flag,sku);
–>explain解释：
+—-+————-+———+——+—————+——+———+——+——+——-+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+—-+————-+———+——+—————+——+———+——+——+——-+
| 1 | SIMPLE | servers | ALL | NULL | NULL | NULL | NULL | 1 | NULL |
+—-+————-+———+——+—————+——+———+——+——+——-+
select_type：查询中每个select子句的类型
(1) SIMPLE(简单SELECT,不使用UNION或子查询等)
(2) PRIMARY(查询中若包含任何复杂的子部分,最外层的select被标记为PRIMARY)
(3) UNION(UNION中的第二个或后面的SELECT语句)。。。
type：访问类型：ALL, index, range, ref, eq_ref, const, system, NULL（从左到右，性能从差到好）
Extra：
(1) Using filesort:MySQL需要额外的一次传递,以找出如何按排序顺序检索行。
(2) Using index:从只使用索引树中的信息而不需要进一步搜索读取实际的行来检索表中的列信息。
(3) Using temporary:为了解决查询,MySQL需要创建一个临时表来容纳结果。
(4) Using where:WHERE 子句用于限制哪一个行匹配下一个表或发送到客户。
-以fis_outin_store表为例：
idx_fis_outin_store_union_2 (process_id,direction,biz_type),
idx_fis_outin_store_union_1 (sku,biz_no,add_time)
idx_fis_outin_store_union_3 (biz_no,sku,fabric_id)
1. 全值匹配

2. 匹配最左列

未形成最左匹配的情况：


3. 匹配列前缀
一般多用于模糊查询

4．范围查询

范围查询必须是最左前缀，而且范围列后面的列无法用到索引。

同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。

注意：仅用explain可能无法区分范围索引和多值匹配。而且between并不意味着就是范围查询。如下图

看起来是用了两个范围查询，但作用于fabric_id上的“BETWEEN”实际上相当于“IN”，实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此要谨慎地区分多值匹配和范围匹配。
5.排序匹配查询

排序顺序跟创建索引顺序不一致，导致出现Using filesort

未出现Using filesort，因为sku视为常量，在排序中被优化，所以索引未颠倒
6.分组匹配查询

7. 覆盖索引

查询时，要查询的列刚好与使用的索引列完全一致，mysql直接扫描索引，然后就可返回数据，大大提高效率，因为不需再去原表查询、过滤，这种形式下的索引称作覆盖索引。
本质原因：上面所说的BTREE索引存储了原表数据。
8. 索引区分度与前缀索引
索引区分度，也叫索引的选择性。因为索引虽然加快了查询速度，但索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，所以一些情况下不适合建立索引。
A、表数据较少；B、索引区分度低。
索引区分度=不重复的索引值/表的记录数。
COUNT(DISTINCT(字段))/COUNT(*)

索引(fabric_id,sku)的区分度很高，但是两者加起来的长度较长，维护起来消耗资源，就有了对应的前缀索引。

前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于覆盖索引。

–>为什么是最左匹配原则：
如表中含有两个字段：（name,cid）

mysql创建复合索引的规则是首先会对复合索引的最左边的，也就是第一个name字段的数据进行排序，在第一个字段的排序基础上，然后再对后面第二个的cid字段进行排序。
第一个name字段是绝对有序的，第二字段就是无序的了。所以通常情况下直接使用第二个cid字段进行条件判断是用不到索引的。这就是所谓的mysql为什么要强调最左前缀原则的原因。

————>总结：
**创建索引的一些原则：
1、最左前缀匹配原则，非常重要的原则
2、=和in可以乱序
3、尽量选择区分度高的列作为索引
4、索引列不能参与计算，保持列“干净”
5、尽量的扩展索引，不要新建索引
不会使用索引的一些场景：
1、以%开头的like查询
2、数据类型出现隐式转化，不会使用索引
3、组合索引，不满足最左原则，不使用符合索引
4、估计使用索引比全表扫描还慢，则不要使用索引
5、用or分割条件，若or前后只要有一个列没有索引，就都不会用索引
6、负向查询（not , not in, not like, <>, != ,!>,!< ） 不会使用索引
7、在条件中使用函数表达式或进行运算等，不会使用索引**

sql优化器会在索引存在的情况下，通过符合 RANGE 范围的条数和总数的比例来选择是使用索引还是进行全表遍历