MySQL 索引此博客不是对索引技术的底层进行讲解仅仅讲解初阶知识方便理解索引和了解索引原理不涉及底层与深层次知识之后可能会写在使用 MySQL 的场景下数据库往往存储着海量数据几万条、几百万条甚至上千万条。如果不对数据做任何处理查询时就只能从头到尾逐行遍历全表扫描时间效率极低。 就像一本几千页的书没有目录我们想找到某一页内容只能从头翻到尾。索引的出现很好地解决了这个问题。它本质上是一种数据结构能够帮助数据库在不扫描全部数据的情况下快速定位到目标记录。后面我们将结合原理和实验来深入理解。1. 没有索引会怎样MySQL 的数据最终是持久化存储在磁盘文件中的例如 InnoDB 引擎的独立表空间.ibd文件或系统共享表空间。因此对表进行增删改查本质上都会涉及磁盘 I/O。而磁盘 I/O 的瓶颈在于机械硬盘存在磁头寻道和盘片旋转延迟随机读取效率很低即使使用 SSD其读写速度也与内存相差几个数量级InnoDB 以页默认 16KB为单位读取数据如果目标记录分散在不同页中会产生大量随机 I/O。如果没有索引查询就必须进行全表扫描将磁盘上的数据页逐页加载到内存再逐行比对筛选。对于 800 万量级的表这意味着可能要加载数百 MB 甚至上 GB 的数据。如果此时再叠加高并发磁盘 I/O 和 CPU 资源会被迅速耗尽系统基本丧失可用性。因此索引不是可选项而是大数据量下保证查询性能的必需品。实验预告下文将基于 800 万条测试数据对比有索引和无索引情况下的查询性能差异直观感受索引的作用。-- -- 0. 开启函数创建权限MySQL 8.0 必需只需执行一次 -- SET GLOBAL log_bin_trust_function_creators 1; -- -- 1. 创建 EMP 表根据插入字段推断的表结构 -- DROP TABLE IF EXISTS EMP; CREATE TABLE EMP ( empno INT PRIMARY KEY, ename VARCHAR(255), job VARCHAR(255), mgr INT, hiredate DATE, sal DECIMAL(10,2), comm DECIMAL(10,2), deptno INT ); -- -- 2. 创建随机字符串函数 -- DELIMITER $$ CREATE FUNCTION rand_string(n INT) RETURNS VARCHAR(255) BEGIN DECLARE chars_str VARCHAR(100) DEFAULT abcdefghijklmnopqrstuvwxyzABCDEFJHIJKLMNOPQRSTUVWXYZ; DECLARE return_str VARCHAR(255) DEFAULT ; DECLARE i INT DEFAULT 0; WHILE i n DO SET return_str CONCAT(return_str, SUBSTRING(chars_str, FLOOR(1 RAND() * 52), 1)); SET i i 1; END WHILE; RETURN return_str; END $$ DELIMITER ; -- -- 3. 创建随机数字函数 -- DELIMITER $$ CREATE FUNCTION rand_num() RETURNS INT(5) BEGIN DECLARE i INT DEFAULT 0; SET i FLOOR(10 RAND() * 500); RETURN i; END $$ DELIMITER ; -- -- 4. 创建批量插入存储过程 -- DELIMITER $$ CREATE PROCEDURE insert_emp(IN start INT(10), IN max_num INT(10)) BEGIN DECLARE i INT DEFAULT 0; SET autocommit 0; REPEAT SET i i 1; INSERT INTO EMP VALUES ( (start i), rand_string(6), SALESMAN, 0001, CURDATE(), 2000, 400, rand_num() ); UNTIL i max_num END REPEAT; COMMIT; END $$ DELIMITER ; -- -- 5. 执行存储过程插入 8000000 条记录 -- CALL insert_emp(100001, 8000000);查询未设置索引的列用时 6.95 秒查询构建索引的列用时 10 毫秒以内。可以明确观察到是否构建索引对大数据量的查找造成了数量级的差距如果再叠加并发场景未设置索引基本不可用。2. 除了索引MySQL 还做了哪些努力索引能帮我们快速定位数据但定位之后数据终究要从磁盘读到内存。为了尽可能减少真正的磁盘 I/OMySQLInnoDB 引擎在索引之外还做了以下关键设计InnoDB 以 16KB「页」为单位与磁盘交互InnoDB 管理数据的最小存储单元叫做Page页默认大小为16KB。为什么不是一条一条读而是整页读因为数据在磁盘上通常是连续存储的尤其是主键顺序插入时。一次 I/O 读取 16KB可能就把目标记录附近的相邻数据也加载进来了。这利用了空间局部性原理用一次 I/O 换多次潜在的内存命中。作为对比操作系统文件系统的块Block通常默认是 4KB但 InnoDB 的页大小是独立配置的innodb_page_size默认 16KB 是数据库场景下权衡后的结果。Buffer Pool —— 在内存中缓存数据页磁盘 I/O 和内存操作的速度差了几个数量级。InnoDB 在启动时会向操作系统申请一大块内存叫做Buffer Pool用来缓存从磁盘读来的数据页。读数据先查 Buffer Pool命中就直接返回逻辑 I/O未命中才去磁盘读取真实页物理 I/O。写数据先修改 Buffer Pool 中的页此时这个页就变成了脏页Dirty Page。脏页不会立刻写回磁盘而是由后台线程Page Cleaner在合适的时机批量刷盘。这种延迟写策略把大量随机磁盘写转化成了内存写 批量顺序刷盘极大提升了吞吐量。索引解决的是如何快速找到数据在哪而以上设计解决的是找到之后如何尽可能少读磁盘、少写磁盘。两者结合才构成了 MySQL 在海量数据下依然能高效运转的完整图景。3. 理解索引从页到 B 树前面提到InnoDB 以16KB 的页为单位管理数据。那么当表中有 800 万条记录、分布在成千上万个页中时如何快速找到目标记录答案藏在两个层次页内如何快速定位记录以及页与页之间如何快速定位。3.1 页内Page Directory页目录先回到单个页。一页 16KB可能存储几十到几百条记录。如果页内只能从头到尾扫描就算确定了目标页查找效率依然很低。InnoDB 的解决方案是在每个数据页的尾部维护一个Page Directory页目录也叫槽Slot。它记录了页内部分记录的偏移位置且这些记录是按主键有序的。当需要在页内查找某条记录时MySQL 会先在 Page Directory 中二分查找快速定位到包含目标记录的槽再在该槽对应的小范围内遍历。这样就把页内全表扫描变成了页内二分查找。但这只能解决一个页内部的问题。当数据量增大需要成千上万个页时页与页之间又该如何组织3.2 页间没有索引时只能线性遍历当多个页存储数据时InnoDB 用双向链表将它们按主键顺序连接起来页头中的FIL_PAGE_PREV和FIL_PAGE_NEXT指针。此时如果没有任何索引查询就只能从第一个页开始沿着链表顺序遍历直到找到目标记录。如果有 1000 万条数据分散在几万个页中这种线性遍历的代价依然是不可接受的。能不能像书的目录一样给这些页也建立一个目录呢3.3 给页建立目录B 树的雏形答案是肯定的。MySQL 引入了一种分层目录的结构最底层的页叶子节点存放真实的用户数据上层的页非叶子节点不存数据只存两样东西键值指向子页的指针。具体规则是每个非叶子节点中的目录项存放的是其指向的子页中最小的键值或键值范围。当需要查找某条记录时从根节点出发比较键值确定目标记录应该落在哪个子页沿着指针进入子页如果子页还是非叶子节点重复步骤 1~2直到进入叶子节点在页内通过 Page Directory 定位具体记录。这样每一次比较都能排除掉一整棵子树的数据而不是一条条比对。3.4 最终形态B 树随着数据量增长目录项也会变多。当根节点存不下时就再往上抽一层形成多级索引。最终这棵树就演变成了B 树B 树有几个至关重要的特征决定了它为什么适合数据库索引非叶子节点不存数据只存键值和指针这意味着一个 16KB 的页能存下成百上千个指针而不是只能存几十条数据。树变得非常矮胖。所有真实数据都存放在叶子节点保证了查询的稳定性不管查哪条数据I/O 次数都差不多树的高度次。叶子节点之间用双向链表连接这让范围查询BETWEEN、、极其高效找到左边界后直接顺着链表向后遍历无需回退到上层节点。3.5 一个直观的计算假设一行数据约 500 字节一个 16KB 的叶子页大约能存32 条记录。非叶子节点只存主键假设 INT 占 4 字节和页指针约 6 字节一个 16KB 页大约能存1600 个目录项。那么2 层 B 树1600 × 32 ≈5 万条记录3 层 B 树1600 × 1600 × 32 ≈8000 万条记录这意味着对于 800 万数据的表B 树的高度通常只有3 层。即使目标数据在磁盘上最多也只需要3 次磁盘 I/O就能定位到这和不建索引时的全表扫描可能需要几万次 I/O相比差距是数量级的。3.6 为什么别的数据结构不行链表链表线性遍历无法实现跨越式的筛选最终的时间效率仍然不可观二叉搜索树有退化问题可能退化成线性结构AVL 和 红黑树虽然是平衡或者近似平衡但是毕竟是二叉结构相比较多阶 B意味着树整体过高大家都是自顶向下找层高越低意味着系统与硬盘更少的 IO Page 交互。虽然很优秀但是有更加优秀的选择。Hash官方的索引实现方式中 MySQL 是支持 HASH 的Hash 跟其算法特征决定了虽然有时候也很快 (O(1))不过在面对范围查找就明显不行另外还有其他差别有兴趣可以查一下。最值得比较的是 InnoDB 为何不用 B树 作为底层索引B树B树B树节点既有数据又有 Page 指针而 B 只有叶子节点有数据其他目录页只有键值和 Page 指针。B叶子节点全部相连而 B 树 没有。为何选择 B 树呢两树的本质区别在于 “非叶子节点是否存储data”如果非叶子节点不对 data 进行存储空间就可以存储更多的目录页从而使得树更矮所以IO操作次数更少。并且叶子节点相连更便于进行范围查找。综上所述使用 B 树实现更佳。3.7 小结创建索引本质上就是在构建一棵 B 树针对 InnoDB 的主键索引而言。B 树通过矮胖的结构和页间目录把全表扫描变成了树的高度次 I/O。索引解决的是数据在哪个页的问题而 Page Directory 解决的是数据在页内的哪个位置的问题。两者配合才完成了最终的快速定位。4. 聚簇索引 VS 非聚簇索引MyISAM 引擎同样使用 B 树作为索引结构叶节点的 data 域存放的是数据记录的地址。下图为 MyISAM 表的主索引 Col1 为主键。其中 MyISAM 最大的特点是将索引 Page 和数据 Page 分离也就是叶子节点没有数据只有对应数据的地址。相较于 InnoDB 索引 InnoDB 是将索引和数据放在一起的。InnoDB 这种用户数据与索引数据在一起索引方案叫做聚簇索引。5. 辅助索引与回表MySQL 除了默认会建立主键索引外我们用户也有可能建立按照其他列信息建立的索引一般这种索引可以叫做辅助普通索引。对于 MyISAM ,建立辅助普通索引和主键索引没有差别无非就是主键不能重复而非主键可重复。下图就是基于 MyISAM 的 Col2 建立的索引和主键索引没有差别同样 InnoDB 除了主键索引用户也会建立辅助普通索引我们以上表中的 Col3 建立对应的辅助索引如下图可以看到 InnoDB 的非主键索引中叶子节点并没有数据而只有对应记录的 key 值。所以通过辅助普通索引找到目标记录需要两次索引查找首先检索辅助索引获得主键然后用主键到主索引中检索获得记录。这种过程就叫做回表查询为何 InnoDB 针对这种辅助普通索引的场景不给叶子节点也附上数据呢原因就是太浪费空间了。