innodb 04 索引-B+树索引

向右看齐 2023-01-05 12:08 277阅读 0赞

#### 索引：若索引太多，应用程序的性能可能会受到影响。而索引太少，对查询性能又会产生影响 ####

## 索引概述 ##

InnoDB存储引擎支持以下几种常见的索引：  
B+树索引  
全文索引  
哈希索引  
InnoDB存储引擎支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。

B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。将其读到内存中，  
查找具体某一个记录：是二分查找page dictory。

## 1、B+ 树索引 ##

B+树索引可以分为聚集索引（clustered inex）和辅助索引，聚集索引与辅助索引不同的是，叶子节点存放的是否是一整行的信息。

#### 聚集索引： ####

聚集索引的叶子节点也被称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。  
同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。  
很多文档会说：聚集索引按照顺序物理地存储数据。但是试想一下，如果聚集索引必须按照特定顺序存放物理记录，则维护成本显得非常之高。  
所以，聚集索引的存储并不是物理上连续的，而是逻辑上连续的。

#### 辅助索引： ####

叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签。  
如果在一棵高度为3的辅助索引树中查找数据，那需要对这棵辅助索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO访问

#### B+树索引的分裂： ####

B+树索引页的分裂并不总是从页的中间记录开始，这样可能会导致页空间的浪费。

InnoDB存储引擎的Page Header有以下几个部分用来保存插入的顺序信息：  
PAGE\_LAST\_INSERT：最后插入记录的位置。  
PAGE\_DIRECTION：记录插入的方向。假如新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就是PAGE\_DIRECTION。  
PAGE\_N\_DIRECTION：假设连续几次插入新记录的方向都是一致的，InnoDBhi把沿着同一个方向插入记录的条数记下来，这个条数就用PAGE\_N\_DIRECTION这个状态表示。当然，如果最后一条记录的插入方向改变了的话，这个状态的值会被清零重新统计。

通过这些信息：innodb决定向左还是向右进行分裂，同时决定将分裂点记录为哪一个

如果插入随机：取页的中间记录作为分裂点的记录，这和之前介绍的相同  
如果非随机：假设页一种有5个位置。如果插入位置是6，那么插入位置是分裂点，直接分裂到下一页。如果插入位置是1，那么3是分裂点，45在下一页。

#### 2、索引的管理 ####

索引的创建和删除可以通过两种方法，一种是ALTER TABLE，另一种是CREATE/DROP INDEX。  
索引的查看：show index from tablename  
查看结果：表名、是否是唯一索引、索引名字、Cardinality等。  
其中Cardinality非常关键的值，表示索引中唯一值的数目的估计值。Cardinality表的行数应尽可能接近1，如果非常小，那么用户需要考虑是否可以删除此索引。

Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新的，即并非每次索引的更新都会更新该值，因为这样代价太大了。  
如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令。

#### 3、索引的创建和删除 ####

旧innodb创建索引过程：创建新表替换原表。  
首先创建一张新的临时表，表结构为通过命令ALTER TABLE新定义的结构。  
然后把原表中数据导入到临时表。  
接着删除原表。  
最后把临时表重名为原来的表名。

后来对于辅助索引:创建的时候对表上S锁。  
主键索引的创建和删除仍然需要临时表替换。

通过新的ALTER TABLE语法，用户可以选择索引的创建方式：  
ALTER　TABLE tbl\_name  
|ADD\{INDEX|KEY\}\[index\_name\]  
index\_type\[index\_option\]…  
ALGORITHM\[=\]\{DEFAULT|INPLACE|COPY\}  
LOCK\[=\]\{DEFAULT|NONE|SHARED|EXCLUSIVE\}  
ALGORITHM指定了创建或删除索引的算法。copy是创建临时表，DEFAULT是默认INPLACE。即不创建临时表。  
LOCK部分为索引创建或删除时对表添加锁的情况：NONE、SHARE(S)、EXCLUSIVE(X)、DEFAULT(尝试N->S->X)

InnoDB存储引擎实现Online DDL的原理是在执行创建或者删除操作的同时，将INSERT、UPDATE、DELETE这类DML操作日志写入到一个缓存中。待完成索引创建后再将重做应用到表上，以此达到数据的一致性。

#### 4、Cardinality ####

Cardinality值非常关键，表示索引中不重复记录数量的预估值。  
实际应用中，Cardinality/n\_rows\_in\_table应尽可能地接近1。如果非常小，那么用户需要考虑是否还有必要创建这个索引。

数据库对于Cardinality的统计都是通过采样（Sample）的方法来完成的。  
采样时机：  
表中1/16的数据已发生过变化。  
stat\_modified\_counter＞2 000 000 000。  
采样方法：  
取得B+树索引中叶子节点的数量，记为A。  
随机取得B+树索引中的8个叶子节点。统计每个页不同记录的个数，即为P1，P2，…，P8。  
根据采样信息给出Cardinality的预估值：Cardinality=（P1+P2+…+P8）\*A/8。

#### 5、联合索引，最左原则。 ####

#### 6、覆盖索引： ####

InnoDB存储引擎支持覆盖索引（covering index，或称索引覆盖），即从辅助索引中就可以得到查询的记录，那就将不会再去搜索聚集索引。

#### 7、优化 ####

**a:某些情况下**，优化器可能并没有选择索引查看数据，而是通过扫描聚集索引，也就是直接进行全表的扫描来得到数据。（多发于范围查找，join连接的情况下。）  
如果要求访问的数据量很小，则优化器还是会选择辅助索引，但是当访问的数据占整个表中数据的蛮大一部分时（一般是20%左右），优化器会选择通过聚集索引来查找数据。因为之前已经提到过，顺序读要远远快于离散读。

索引提示：显式地告诉优化器使用哪个索引。  
使用时机：优化器选择了错误的索引，导致运行缓慢(非常少见)。sql语句可以选择的索引非常多，优化器选择执行计划的开销可能大于sql本身  
using index语法：SELECT*FROM t USE INDEX(a)WHERE a=1 AND b=2;。USE INDEX只是告诉优化器可以选择该索引，实际上优化器还是会再根据自己的判断进行选择  
force index语法：SELECT*FROM t FORCE INDEX(a)WHERE a=1 AND b=2;force index指定了要使用哪个索引。

**b:MRR优化：**  
好处：  
MRR使数据访问变得较为顺序。在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序的顺序进行书签查找。  
减少缓冲池中页被替换的次数。  
批量处理对键值的查询操作。  
过程：  
将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据是根据辅助索引键值排序的。  
将缓存中的键值根据RowID进行排序。  
根据RowID的排序顺序来访问实际的数据文件。  
案例：  
MRR还可能把某些范围查询拆分为键值对：where 2<a and a<5 and b =3。可能不是范围查询，而是查询\[3,3\] \[4 ,3\]。

**c: icp优化**  
当进行索引查询时，首先根据索引来查找记录，然后再根据WHERE条件来过滤记录。在支持Index Condition Pushdown后，MySQL数据库会在取出索引的同时，判断是否可以进行WHERE条件的过滤，也就是将WHERE的部分过滤操作放在了存储引擎层。

在某些查询下，可以大大减少上层SQL层对记录的索取。