深入浅出索引

索引的出现是为了提高查询的效率，类似书的目录。对于数据库的表而言，索引就是它的目录。

索引的常见模型

哈希表、有序数组、搜索树。

哈希表-Memcached

哈希表是一种以键-值(key-value)存储数据的结构，只需要输入待查找的键，就可以找到其对应的值。把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。支持随机增删改查，key不是递增有序的，书序读取区间查找速度慢。

多个key值经过哈希函数的换算，会出现同一个值的情况。哈希冲突，链表/开放寻址。

哈希表适用于只有等值查询的场景。

有序数组

数组按照id递增的顺序保存，在等值查询和范围查询场景中的性能都非常优秀用。二分查找可以快速找到指定id对应的数据时间复杂度为O(logn)。范围查询，先用二分法找到左区间开始位置，然后向后遍历即可。插入数据必须挪动后面所有的记录，成本贵太高。

有序数组使用于静态存储引擎。

二叉搜索树-MySQL

每个节点的左儿子小于父节点，父节点又小于右儿子。查找指定id对应的数据的时间复杂度为o(logn)。为了维持O(logn)的查询复杂度，需要保持树是平衡二叉树，更新的时间复杂度为O(logn)。

二叉树，大数据量树高过高，会产生多次磁盘IO。
扩展为N叉树，N叉树中的N取决于数据块的大小。
树高取决于叶子树（数据行数）和“N叉树”的N。而N是由页大小和索引大小决定的。

N叉树N的值。5.6以后可以通过page的大小（默认16KB）来间接控制。
（键为整型4个字节（长整形8个字节）时，加上辅助数据（指针固定6个字节）及其他，差不多每个键key占13字节，16KB/13B，非叶子节点能存储1200个建，1200叉树）

N叉树读写性能优良，适配磁盘的访问模式，广泛应用于数据库引擎。

B+树支持顺序扫描。能够很好的配合磁盘的读写特性（局部性原则-缓存），减少单次查询的磁盘访问次数。树根的数据块存储在内存中(少一次磁盘IO)。

数据结构与算法-B+树

跳表-Redis

数据结构与算法-跳表

LSM树-HBase

牺牲读性能，提高写性能。
LSM(Log Structured Merge Tree)将磁盘随机写转化为顺序写。把一棵大树拆分成N棵小树，将对数据的修改增量保存在内存中，达到指定大小限制后批量把数据flush到磁盘中，磁盘中定期做merge操作，合并成一棵大树，以优化读性能。

InnoDB的索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB使用了B+树索引模型，数据都是存储在B+树中的（有序）。（树中的节点并不存储数据本身，而是只是作为索引。叶子节点存储数据，把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。）

B+树的每个节点都是一页，最上层的根节点单独一页。
B+树的叶子节点存储的是page(页，默认大小16k)，一个页里面可以存多个行。
索引只能定位到page，page内部有个有序数组，二分法定位行数据。

每一个索引在InnoDB里面对应一棵B+树。一张表可以有多个索引。

根据叶子节点的内容，索引类型分为主键索引和非主键索引。

主键索引

主键索引的叶子节点value存的是整行数据（一页16K，可以存多行。整张表的数据其实存在主键索引中。是数据不是地址）。在InnoDB里，主键索引也被称为聚簇索引(clustered index)。

主键查询方式，只需要搜索主键对应的B+树，就可以获得数据。(树节点的key是某行主键，value是该行数据。)

非主键索引

非主键索引的叶子节点内容是主键的值（每个叶子节点是一个数据页，每个数据页16K,存放多个主键值）。在InnoDB里，非主键索引也被称为二级索引(secondary index)。

普通索引查询方式，需要先搜索普通索引树，得到主键的值，再到主键索引树搜索一次。这个过程称为回表。(基于非主键索引的查询多扫描一棵索引树，每条查出的数据都要分别回表。当然只需要主键的值，就不需要回表)

InnoDB会把主键字段放在普通索引字段后面，同时会去重。(二级索引中的主键会依次进行排序)

当主键是(a,b)的时候，
定义为c的索引，实际上是(c,a,b);
定义为(c,a)的索引，实际上是(c,a,a,b)–>(c,a,b);
定义为(c,b)的索引，实际上是(c,b,a,b)–>(c,b,a);– 回表时自动交换a,b列来查找对应的主键值

索引维护

页分裂

B+树为了维护索引有序性，在插入新值的时候需要做必要的维护—移动数据(追加新增递增插入时，不需要移动数据，不会页分裂)。如果原来所在的数据页已经满了，根据B+树的算法，需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。（每个页面之间是用指针串的。分裂时只需要改指针指向。）

页分裂操作不仅影响性能，还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%。

页合并

当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

没有主键的表，InnoDB会默认创建一个Rowid做主键。

自增主键

自增主键的插入数据模式：插入新纪录的时候可以不指定ID的值，系统会获取当前ID最大值加1作为下一条记录的ID值。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。（一个页满了，就申请另外一个页面从左边开始写数据。）

1 2	-- 自增主键是指自增列上定义的主键。主键天然是索引，不用显示指定index not null primary key quto_increment

业务逻辑主键

业务逻辑的字段做主键，不容易保证有序插入，写数据成本高。
每个非主键索引的叶子节点上都是主键的值。如果用业务逻辑字段做主键，叶子节点占用空间一般比整型（4字节）或长整型（8字节）自增主键占用的空间大。

只有一个索引；该索引必须是唯一索引。适合用业务字段直接做主键。
典型的KV场景（没有range操作），由于没有其他索引，不用考虑其他索引的叶子节点大小的问题。利用尽量使用主键查询的原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

索引可能因为删除、或者页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面利用率最高，索引更紧凑、更省空间。

-- 关键字index 与 key无区别
-- 删除并重建普通索引  
alter table T drop index k;
alter table T add index(k);
-- 删除重建主键索引  
alter table T drop primary key;
alter table T add primary key(id);
-- 删除主键或者创建主键，都会将整个表重建，导致普通索引失效  
alter table T engine = InnoDB;

覆盖索引

回到主键索引树搜索的过程，称为回表。查询结果所需要的的数据只在主键索引上有，不得不回表。

在查询里面，要查询的值已经在普通索引树上了，可以直接提供查询结果，不需要回表。普通索引已经“覆盖了”查询需求，称为覆盖索引。（select返回部分的列+where条件条件的列）
覆盖索引可以减少树的搜索次数，显著提升查询性能，使用覆盖索引是一个常用的性能优化手段。（维护性能下降）

基于B+树的结构，对于范围查找between and，索引定位到左边界后遍历直到不满足条件。(且对于二级索引边扫描边回表搜索，有mrr(Multi-Range Read Optimization)优化就一起回表)
where条件in语句走对应字段的索引，把in里面的条件挨个循环走一遍索引。

最左前缀原则-联合索引

B+树这种索引结构，可以利用索引的“最左前缀”，来定位记录。

不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。
最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

InnoDB的每个普通索引（叶子节点存的是主键值），都相当于这个索引字段和主键字段的联合索引。联合索引按照联合字段定义的先后顺序，依次进行排序存储。(避免order by再排序，先排序再回表)~~非叶子节点只是第一个关键字的索引(所以只有第一个关键字能用到快速定位)~~。非叶子节点存储的对应联合索引各个字段，叶子节点在非叶子基础上加上主键字段。

建立联合索引，安排索引内字段顺序的原则：

如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。
既有联合查询，又有基于各个字段的各自查询，查询条件只有后面字段的查询无法用到联合索引，需要针对后面字段再单独建立索引。联合索引字段的先后顺序，考虑空间占用，字段大的放前面跟小字段建立联合索引，字段小的再建立单字段索引。

如果查询顺序和联合索引的顺序不一致，优化器会自动做优化。查询语句中的where里面各个判断调换顺序无影响。

index_merge，合并索引优化，有临时表消耗。

select * from T where name like 'j' 或 'j%' 或 '%j' 或 '%j%' 使用name索引的问题(主键id)：
a. 只有 id 和 name 字段。
b. 添加了 age 字段，即 id、name、age 字段。

1. like 'j' 或 'j%' 可以使用name索引，并且快速定位记录。
2. like '%j' 或 '%j%'，只是在name二级索引树上遍历查找记录，并不能快速定位（扫描了整棵索引树）。
3. 只有 id 和 name 字段时，上述 4 种 like 查询，name 索引能满足 id 和 name 的查询情况，不需要回表，所以选择了使用 name 的索引树解决问题。

4. 添加了 age 但无联合索引 (name, age) 的情况，如果使用 name 索引树，需要回表。再 like '%j' 或 '%j%' 直接扫描主键索引树，现象就是没有使用 name 索引。
5. 添加了 age 字段，也添加了 (name, age) 索引，和第 3 点同理，使用覆盖索引就能满足 select * 的字段查询，不需要回表，因此使用了 (name, age) 索引树。但是只有 like 'j' 和 'j%'能快速定位记录，而 like '%j' 和 '%j%' 也能使用该索引树，但是不能快速定位，需要顺序遍历。
-- 针对联合索引，左侧字段的条件必须是=，不能是大于或者小于等范围值、不等于（!= <>）、is null is not null，否则右侧字段用不上。  
-- 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。（不能用索引快速定位）

索引下推

不符合最左前缀的部分。索引下推（index condition pushdown）需要server层和引擎层配合。
联合索引（name,age），查询 name like ‘张%’ and age = 10的记录。

用到联合索引找到张开头的记录。
判断其他条件
2.1 MySQL5.6之前，只能从得到的‘张’开头的记录开始（根本不看联合索引中其他字段的值），一个个回表，到主键索引上找出数据行，再对比其他字段值。
2.2 MySQL5.6引入索引下推（引擎层）优化(index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录（不是快速定位，只是快速过滤），减少回表次数。（索引下推其实是把条件判断提前了）

扫描行数问题，在引擎内部读取了多条记录，在server层只拿到了符合条件的记录，而扫描行数统计结果以server层的为主了。