Mysql索引

一、什么是索引

索引是一种可以提高数据查询效率的数据结构，常见的能够提高查询效率的数据结构有哈希表、有序数据、搜索树。哈希表是一种以键值对存储数据的结构，它的查询效率很高，时间复杂的是O(1)，但是只能支持等值查询，不支持范围搜索。有序数组在等值查询和范围查询场景中的性能都非常优秀，时间复杂度是O(log(N))，但是数组结构更新数据性能比较差，插入一个记录需要移动后面所有的记录。搜索树相对来说就比较全面，支持范围查询，查询和更新的时间复杂度都是O(log(N))。

二、为什么InnoDB的索引是B+树

搜索树有二叉树、B树、B+树等，二叉树的查询效率是最高的，那为什么数据库的索引用的却是B+树呢？因为索引数据不止在内存中还会写入磁盘，数据查询的时间主要依赖磁盘 IO 的次数，树的深度越大，查找次数越多，性能就会越差，所以要尽量使用多叉树。

一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 200 ms 的时间，性能非常差。 而对于InnoDB的整数字段索引为例，这个 N 差不多是 1200，也就是1200叉树，这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。

B树就是普通的多叉树，每个节点都会存储索引Key、行数据和指向下一个节点的指针。B+树是B树的改进，只有叶子节点才会存储行数据，非叶子节点只存储索引Key和指针。因为所有数据都在B+树的叶子节点，所以每个叶子节点能存储的索引记录更多，所以树形更加矮胖，高度更小，查询产生的I/O最少 ；并且B+树使用双向链表串连所有叶子节点，区间查询效率更高，而B树则需要通过中序遍历。

三、InnoDB索引结构

索引B+Tree结构

InnoDB在通过索引去查询数据时时都会把索引记录所在的页从磁盘加载到内存。InnoDB默认数据页大小16K，可以通过Innodb_page_size进行设置，B+树索引中每个节点就是一页。同层的页通过前后指针构成了一个双向链表。

一个整数（bigint）字段的索引，每条记录索引键的长度为8B，加上指向子页的指针6B，可以算出 16K/14B ≈ 1170，那么这棵B+树大约有1170叉。这里索引节点大小的计算我理解是不准确的，对于非叶子节点索引记录的大小=Key+指向子页的指针+指向下条记录的指针+头信息。叶子节点索引记录大小=数据行信息大小+指向下条记录的指针+头信息

这里有一个问题，通过索引去查询数据的时候，可以通过页指针去找到记录所在的页，时间复杂度是O(LogN)，但是到了具体的页之后只能通过链表去查找，虽然是在内存中，但每页可能有1000条记录，还是会影响性能。这里InnoDB已经做了处理，我们后面再看。

页节点结构

索引页中的记录通过Next Record(页中的内存偏倚量)构成了一个单向链表，除了插入的3条记录外，还多了Infimum&Supremum记录，这是因为B+树需要增加节点申请新页时会插入Infimum最小记录和Supremum最大记录，同时Infimum Next Record指向本页中键最小的记录，而本页中键最大的记录Next Record则指向Supremum。

Record size = 5 (header,其中Next Record占2字节) + 4 (PK) + 6 (TRX_ID) + 7 (ROLL_PTR) + 10 (non-key fifields) = 32 bytes

索引页目录

前面说到在页内查询记录的问题，看下InnoDB是怎么解决的。将索引页中的记录进行分组，并将组中的最后一条记录选为Slot(槽)，Slot记录上的N_owned表示管理的记录数量，这个数量在4和8之间，其中有两个例外，Infimum Slot只有自己一条记录，N_owned=1，而Supermum Slot管理的记录数量可以小于4。分完组之后，再将Slot按照在索引页中的Offset大小组成一个有序数组，就得到了Page directory （页目录）。这种优化的方式，使用有序数组提高链表的查询速度，也是跳表的实现细想。

再来看下有了Page directory 是怎么通过索引去查询数据的：

比如要查询K=22这条记录，先通过页指针定位到具体的页之后，通过二分法查询Page directory，首次定位到Offset=477的Slot，K=11

删除记录

我们在使用Mysql时可能会发现一个问题，为什么已经把大表的数据删掉很多了，但是数据库的硬盘占用量却还是不变？因为Mysql并没有把数据从硬盘上物理删除，而是将记录头信息中的Deleted字段更新成了On，表示这个记录已经被删除，并将它从记录链表中剔除，添加到Garbage Off链表头部，Garbage Size 表示当前页删除记录大小。

如果继续执行 insert into t values(5, 'abcdefghij')，InnoDB不会在页内申请新的空间，而是直接复用删除的@258记录，并且会将该记录从Garbage Off链表删除。同样的如果页中的记录全被删除，页也可以被复用

?

更新记录

如果更新后的记录大于原记录，会将旧值删除，再插入新值。而且不止是更新、删除操作，插入数据也会造成空洞现象，如果数据是按照索引递增顺序插入的，那么索引是紧凑的。但如果数据是随机插入的，就可能造成索引的数据页分裂，满的页就会留下空洞。

重建表

那么要怎么将这些记录从磁盘上进行删除呢，可以通过alter table A engine=InnoDB 命令来重建表，在Mysql5.6版本之后的Online DDL，可以支持允许对原表进行增删改查的同时进行重建表

1.建立一个临时文件

2.扫描表 A 主键的所有数据页，用数据页中表 A 的记录生成 B+ 树，存储到临时文件中

3.生成临时文件的过程中，将所有对 A 的操作记录在一个日志文件（row log）中

4.临时文件生成后，将日志文件中的操作应用到临时文件，得到一个逻辑数据上与表 A 相同的数据文件

5.用临时文件替换表 A 的数据文件四、InnoDB索引概念介绍

主键索引和普通索引

在InnoDB中，表都是一棵主键索引的B+树，叶子节点存的是整行数据，也叫聚簇索引，而我们建立的普通索引，叶子节点内容是主键的值，也被称为二级索引。

什么是覆盖索引

SQL1：select * from t where name = "a"
SQL2：select id from t where name = "a"

SQL1查询的时候需要先查name的普通索引，得到主键id=0后去主键索引查找R0记录，需要进行回表一次。而SQL2只需要查询id，id的值已经在name的索引树上了，因此可以直接返回结果，不需要回表，这种就是索引，普通索引列上已经包含了需要查询的列信息。

什么是联合索引

如果查询的条件有多个，可以建立联合索引提高查询速度；因为索引会占用存储空间，降低插入、更新的性能，所以一张表上的索引不是越多越好，可以建立联合索引来代替多个单索引。

什么是索引的最左前缀原则

满足索引的最左前缀，就可以利用索引来加速搜索，这个最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左N个字符（like X%）

什么是索引下推(ICP)

ICP(index condition-pushdown) MySQL 5.6 引入的索引优化技术mysql索引表，利用联合索引上的字段进行条件过滤，减少二级索引的回表次数。

官方给的示例：Suppose that a table contains information about people and their addresses and that the table has an index defined as INDEX (zipcode, lastname, firstname). If we know a person's zipcode value but are not sure about the last name, we can search like this:

SELECT * FROM people WHERE zipcode='95054'AND lastname LIKE'%etrunia%'AND address LIKE'%Main Street%';

MySQL can use the index to scan through people with zipcode='95054'. The second part (lastname LIKE '%etrunia%') cannot be used to limit the number of rows that must be scanned, so without Index Condition Pushdown, this query must retrieve full table rows for all people who have zipcode='95054'.

With Index Condition Pushdown, MySQL checks the lastname LIKE '%etrunia%' part before reading the full table row. This avoids reading full rows corresponding to index tuples that match the zipcode condition but not the lastname condition.

数据库大神何登成对索引下推也进行了分析，可以帮助我们更好的分析关于联合索引范围查询的执行情况。

create table t1 (a int primary key, b int, c int, d int, e varchar(20));
create index idx_t1_bcd on t1(b, c, d);
select * from t1 where b >= 2 and b < 8 and c > 1 and d != 4 and e != ‘a’;

上面的查询语句，很显然会走 idx_t1_bcd 联合索引查询，对于where中过滤条件的处理，可以抽象成三种情况：

index key：用于确定SQL查询在索引中的连续范围(起始范围+结束范围)的查询条件，Index Key也被拆分为Index First Key和Index Last Key，分别用于定位索引查找的起始，以及索引查询的终止条件。也就是说根据索引来确定扫描的范围。Index First Key(b >= 2,c > 1)，这里面需要理解下根据联合索引的最左前缀原则，遇到> < != 后续的索引字段就会失效，同样的索引的查询范围条件也要满足这个原则 (对于b >2 和 c > 1 两个限定条件来说，在索引树内 c 是无序的，只有条件 b > 2 有效 )，Index Last Key（b < 8）（同样的如果 b 1 and d != 4 )

table filter： where中的条件不能使用索引进行过滤的，只能访问table，回表进行条件过滤了，table filter ( e != ‘a’ )

在MySQL 5.6之前，并不区分Index Filter与Table Filter，统统将Index First Key与Index Last Key范围内的索引记录，回表读取完整记录，然后返回给MySQL Server层进行过滤。而在MySQL 5.6之后，Index Filter与Table Filter分离，Index Filter下降到InnoDB的索引层面进行过滤，减少了回表与返回MySQL Server层的记录交互开销，提高了SQL的执行效率

唯一索引和普通索引有什么区别

建立索引的原则

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!