MySQL - 索引

平平无奇一码农 2021-06-21

389

索引设计是应用程序设计和开发的重要组成，关系型数据库使用最为频繁的是 B+ 树索引，其中 B 表示的是平衡（balance）。

下面从分析数据结构和算法入手分析 B+ 树索引。

二叉查找树和平衡二叉树

B+ 树是由二叉查找树，再由二叉平衡树，B 树演化而来，在分析 B+ 树之前先从二叉树开始了解。二叉查找树的基本思想是二分查找，二分查找（binary search）亦称折半查找，其思想是将一组数据按序排列，在查找过程中以查找区间中点位置为比较对象跳跃查找，不断折半缩小查找区间。

二叉查找树是一种经典数据结构，上图显示的是一棵二叉查找树，在二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。这意味着可以通过中序遍历得到有序的键值输出，即：2、3、5、6、7、8。通过这棵二叉查找树进行查找其实本质就是二分查找，如查找键值为 5 的记录，查找顺序是 根节点->左子树（3）->右子树（5）
，一共查找三次。

二叉查找树可以任意构造，根据节点插入顺序，相同的一组键值也可能展现出其他的结构，如上图，平均查找次数 (1+2+3+4+5+5)/6=3.16 次，而顺序查找平均查找次数为 (1+2+3+4+5+6)/6=3.3 次，二者效率很接近，但是二叉树带来了更高的复杂度。极端情况，二叉树甚至可能退化成链表，这就无法起到二分查找的作用。

唯一应对二叉查找树退化问题，产生了平衡二叉树，又称 AVL 树。平衡二叉树是在二叉查找树的基础上满足任何节点的两个子树的高度最大差为 1。平衡二叉树具有很好的查询效率，但过于严格的平衡条件导致维护一棵平衡二叉树的代价十分大，通常需要一次或多次旋转来得到插入或更新后树的平衡。

B+ 树

B 树和 B+ 树都是平衡查找树，而且是多路平衡查找树，即每个节点的子树可能超过两个。

一棵 M 阶 B 树，是一颗 M 路平衡查找树或者是一个空树（注：M阶代表一个树节点最多有多少个查找路径），满足以下条件：

所有节点键值按递增排列，并遵循左小右大原则；
每个非叶子节点（除了根）的子节点数量 <= ceil(m/2) 个且 < M 个（注：ceil() 是个朝正无穷方向取整的函数如 ceil(1.1) 结果为 2);
非叶子节点的键值数量是其子节点数量 - 1；
所有叶子节点均在同一层,叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针,只不过其指针地址都为 null。

上图是一个 3 阶 B 树，B 树的的性能总是等价于二分查找（与 M值无关），也就没有 AVL 树平衡的问题。

B+ 树是对 B 树的改进，和 B 树不同在于：

非叶子结点的子树指针与关键字个数相同；
非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i], K[i+1]) 的子树（B-树是开区间）；
所有的非叶子节点都只保存索引，不保存数据，只有叶子节点保存数据；
每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接；
父节点存有右孩子的第一个元素的索引。

B+ 树和 B树相比，非叶子节点并没有保存数据，能够容纳比 B 树更多的非叶子节点，一次性读入内存的的查找范围也就越广，减少 IO 次数。B+ 树所有数据都存储在叶子节点，查询任意节点的路径相同，查询效率更为稳定，而 B 树拥有更快的平均寻址速度。最主要的一点是，B+ 树的所有叶子节点通过指针相连，十分适合范围查找和遍历，对于关系型数据库十分有意义。

聚簇索引

聚簇索引，也称聚集索引，是指根据每张表的主键构建出一棵 B+ 树，叶子节点存放整张表的行记录数据，非叶子节点仅存放键值以及指向数据页的偏移量，这也意味着每张表有且只有一个聚簇索引。

有许多文章这么说：聚簇索引是按照顺序物理地存储数据。但其实在 InnoDB 存储引擎中这样是错误的，如果聚簇索引必须按照特定顺序存放物理记录，维护成本很高昂。所以，InnoDB 存储引擎中聚簇索引是逻辑上连续。

辅助索引

辅助索引，也称非聚集索引，叶子节点不包含行记录的全部数据，仅存储索引字段的键值。此外，辅助索引地叶子节点地索引行中还包含一个书签，用于指示与索引相对应地行记录在哪，也就是相应行记录地聚集索引键。

辅助索引不影响聚簇索引组织，因此辅助索引理论上是没有限制的（实际上，适当数量的辅助索引才能最大提高检索性能）。当通过辅助索引寻找数据，InnoDB 存储引擎会遍历合适的辅助索引，通过书签获得相应行记录在聚簇索引的键，在通过主键索引来找到完整的行记录。

InnoDB 存储引擎支持联合索引，即针对表中的多个字段建立索引。本质上说，联合索引也是一棵 B+ 树，区别于单列索引，联合索引的键值数量不是 1 个。

假设上图是两个整型组成的联合索引，两个键值分别为 a、b。对于查询 SELETC * FROM TABLE WHERE a = XXX AND b = XXX
,显然是可以使用 (a,b) 联合索引的，而且对于单个 a = xxx
查询也可以使用 (a,b) 联合索引，但对于 b = xxx
查询无法使用 (a,b) 联合索引。我们可以看到联合索引上的 b 值为 1、2、1、4、1、2，显然不是有序的。

联合索引还有一个好处是，如(a,b) 联合索引中对第二个键值已经在第一个键值有序的基础上做了排序处理，在很多情况下可以避免在查询时多一次排序操作。

InnoDB 存储引擎还支持覆盖索引，即从辅助索引中可以得到查询的记录，而不需要查询聚簇索引中的记录。这样的优点在于，辅助索引不包含行记录的全量数据，只包含索引字段，可以减少大量的 IO 操作。下面展示覆盖索引的实例。

CREATE TABLE log (
  uid INT(11) NOT NULL,
  udate DATE
)ENGINE=INNODB;


ALTER TABLE log ADD KEY (uid);
ALTER TABLE log ADD KEY (uid,udate);


SHOW INDEX FROM log;


INSERT INTO log VALUES(1,'2009-01-01');
INSERT INTO log VALUES(2,'2010-01-01');
INSERT INTO log VALUES(3,'2019-01-23');
INSERT INTO log VALUES(4,'2001-01-21');
INSERT INTO log VALUES(2,'2009-04-01');
INSERT INTO log VALUES(3,'2009-01-05');
INSERT INTO log VALUES(1,'2009-01-21');
复制

上面建立了 log 表，并建立了两个索引，索引名分别默认为 uid1、uid_2，并插入测试数据，下面展示几条 SQL 的 EXPLAIN 结果。

EXPLAIN SELECT * FROM log;
复制

EXPLAIN SELECT COUNT(*) FROM log;
复制

EXPLAIN SELECT COUNT(*) FROM log WHERE udate > '2008-01-01';
复制

我们可以看到上面的几条 SQL 的执行计划 possible_keys 都为 null，但是 key 实际执行时优化器都选择了索引，在列 Extra 中都出现了 Using index ，这段话含义为覆盖索引。在执行时，优化器认为通过覆盖索引可以获得比聚簇索引更好的效果，尤其是统计查询更容易出现这种情况，借助覆盖索引往往能带来巨大的提升，但索引是很宝贵的，需要甚至考虑。

索引管理

索引创建和删除有两种方式：ALTER TABLE 和 CREATE/DROP INDEX。

-- ALTER TABLE 方式
-- 添加索引
ALTER TABLE <table_name> ADD INDEX <index_name>(column_list);
ALTER TABLE <table_name> ADD UNIQUE(column_list);
ALTER TABLE <table_name> ADD PRIMARY KEY(column_list);
-- 删除索引
ALTER TABLE <table_name> DROP INDEX <index_name>;
ALTER TABLE <table_name> DROP PRIMARY KEY;


-- CREATE/DROP INDEX 方式
-- 添加索引
CREATE INDEX <index_name> ON <table_name>(column_list);
CREATE UNIQUE INDEX <index_name> ON <table_name>(column_list);
-- 删除索引
DROP INDEX <index_name> ON <table_name>;
复制

我们还可以通过 SHOW INDEX FROM TABLE 查看表的索引信息，以 log 表为例。

-- SHOW INDEX FROM <table_name>
SHOW INDEX FROM log;
复制

SHOW INDEX 每列的含义：

Table：索引所在的表名
Non_unique：非唯一的索引。
Key_name：索引的名字。
Seq_in_index：索引中该列的位置。
Column_name：索引列的字段名字。
Collation：列以什么方式存储在索引中。可以是 A 或 NULL。B+ 树索引总是 A，即排序的。
Cardinality：非常关键的值，表示索引中唯一值的数目的估计值。Cardinality 表的行数应尽可能接近 1，如果非常小，那么用户需要考虑是否可以删除此索引。
Sub_part：是否是列的部分被索引。如果这里显示 100，表示该列的前 100 字符进行索引。如果索引整个列，则该字段为 NULL。
Packed：关键字如何被压缩。如果没有被压缩，则为 NULL。
Null：是否索引的列含有 NULL 值。可以看到 uid_2 的 udate 字段该值为 YES，因为定义的列允许 NULL 值。
Index_type：索引的类型。InnoDB 存储引擎只支持 B+ 树索引，所以这里显示的都是BTREE。
Comment：注释。

Cardinality 值十分重要，优化器会根据这个值来判断是否使用这个索引，但这个值的更新不是实时的，如果需要更新索引的 Cardinality 值，可以使用 ANALYZE TABLE 命令进行强制更新。

SELECT
    COUNT(DISTINCT column)  COUNT(*) column
FROM
    TABLE
复制

Cardinality 值表示索引中不重复记录数据的预估值，既然是预估值就不是一个准确值。在实际应用中，如果 Cardinality/n_rows_in_table 应尽可能接近 1，如果非常小，就需要考虑这个索引是否有必要创建。此外我们也可以根据表中字段去重前后的比值来判断该字段是否需要建立索引，道理是类似的。

有时候需要索引字符类型的列，这往往会导致索引变得大且慢，通常我们可以通过索引前 N 位来节约索引空间，虽然这在一定程度上降低了索引的区分度，但在效率上是提升的。

CREATE TABLE user_info (
  name VARCHAR(20) NOT NULL,
  address VARCHAR(100) NOT NULL
)ENGINE=INNODB;


INSERT INTO user_info VALUES('A','AAABBBWWYASDASDSADASWQEY');
INSERT INTO user_info VALUES('B','BBBSSSUUSADASDASBDHASDGG');
INSERT INTO user_info VALUES('C','AAAQQQLLGASHDVAHSVDHASG');
INSERT INTO user_info VALUES('D','AAANNNSSLQWEWNZJKL');
INSERT INTO user_info VALUES('E','AAAWWWVVZVASHDVASHDVAJHDVASHDBVASHDASZ');
INSERT INTO user_info VALUES('F','OOOWWWWSSLKLASDHQHWEQEBZZQ');
INSERT INTO user_info VALUES('G','HHHAAALLLWWASDHBASDBANSBDASW');
INSERT INTO user_info VALUES('H','HJJSSSWWWZAHSDHAGDHASD');
INSERT INTO user_info VALUES('I','GHGJASJJBQJWHEJKQWNEJ');
INSERT INTO user_info VALUES('J','SDGJBWBZKWASHDGAHGQWBEQ');
INSERT INTO user_info VALUES('K','QQJZKSDSADBQKJBQQWHEJNQWBNZ');
INSERT INTO user_info VALUES('L','AGUIQWHEMNZAQHADJABSJHDBAJSBW');
INSERT INTO user_info VALUES('M','AJHQWBEJNZLASDHBQ');
INSERT INTO user_info VALUES('N','ASDBZIOQWNJHASQEJKWQEJKQDH');
INSERT INTO user_info VALUES('O','ASDJKQWHEJQWHEKNAJK');


SELECT
    COUNT(DISTINCT LEFT(address,1))  COUNT(*) address
FROM
    user_info;


SELECT
    COUNT(DISTINCT LEFT(address,2))  COUNT(*) address
FROM
    user_info;


SELECT
    COUNT(DISTINCT LEFT(address,3))  COUNT(*) address
FROM
    user_info;


SELECT
    COUNT(DISTINCT LEFT(address,4)) / COUNT(*) address
FROM
    user_info;
复制

我们可以建立前 N 位索引提升效率较大的索引，上面的例子刚好在前 4 位比值为 1，实际情况可能很难达到，我们建立全列和前 4 位索引，查看执行计划。

CREATE INDEX index_full_address ON user_info(address);
CREATE INDEX index_left4_address ON user_info(address(4));


EXPLAIN SELECT * FROM user_info WHERE address = 'ASDJKQWHE';
复制

我们可以看到，上面的查询实际上走了前缀索引（index_left4_address），但是前缀索引也有缺点，因为前缀索引并没有保存索引字段的全部内容，所以无法使用覆盖所以,而且也无法利用前缀索引进行 GROUP BY 和 ORDER BY。

索引是稀有资源，我们要避免创建冗余索引。假设表中拥有 a、b、c 三个字段，如果建立了（a,b,c）索引，相当于建立了（a）、（a,b）、（a,b,c）三个索引，如果再单独创建（a）索引就是冗余索引。但是如果创建（b）索引则不是冗余索引，因为（b）索引不是（a,b,c）索引的最左前缀。

索引还可以帮助我们锁定更少的行记录，这给我们带来两个好处：一是减少锁行记录的开销；二是减少锁冲突，提高数据库并发能力。

索引优化

MySQL 5.6 版本开始支持 Multi-Range Read（MRR）优化。目的是减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问。MRR 优化可适用于 range、ref、eq_ref 类型的查询，它的好处如下：

较为顺序地访问数据（在查询辅助索引时，首先根据得到的查询结果按照主键进行排序，并按照主键排序的顺序进行书签查找）。
减少缓冲池中页被替换的次数。
批量处理对键值的查询操作（MRR 可以将某些范围查询拆分成键值队来批量查询数据，这样的好处是可以在拆分过程中直接过滤一些不符合条件的数据）。

同 MRR 优化，Index Condition Pushdown（索引条件下推）同样是 MySQL 5.6 版本开始支持的，简称 ICP 优化，这是一种根据索引进行优化的方式。ICP 优化会在取出索引的同时判断是否可以进行 WHERE 条件过滤，也就是将 WHERE 的部分过滤操作放在了存储引擎层面。在 MySQL 5.6 版本之前，并不区分 Index Filter 和 Table Filter，统统将 Index First Key 与 Index Last Key 范围内的索引记录，回表读取完整记录，然后返回给 MySQL Server 层进行过滤。而在 MySQL 5.6 版本之后，Index Filter 与 Table Filter 分离，Index Filter 下降到存储引擎层面进行过滤，减少了回表与返回 MySQL Server 层的记录交互开销，提高了SQL的执行效率。

表的数据可能碎片化，碎片化的索引可能很差或者无序的方式存储在磁盘上，导致查询效率下降。我们可以通过 OPTIMIZE TABLE 重新整理数据，对于那些不支持 OPTIMIZE TABLE 的存储引擎可以通过修改表的存储引擎为当前存储引擎实现重新整理数据,如下：

OPTIMIZE TABLE <tablename>;


ALTER TABLE <tablename> ENGINE = <engine>;
复制

公众号文章同步github。

本文地址：github.com/lazecoding/Note/blob/main/note/articles/mysql/索引.md

mysql

文章转载自平平无奇一码农，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。