目录一、什么是索引二、MySQL索引数据结构的选择2.1. 为什么不用二叉查找树 / 红黑树2.2. 为什么不用哈希表Hash2.3. B 树B-Tree的妥协与痛点2.4. B 树MySQL 的选择BTree和BTree对比三、 聚簇索引 vs 非聚簇索引1. 聚簇索引Clustered Index / 主键索引2. 非聚簇索引Secondary Index / 辅助索引 / 二级索引四、 回表LookupSQL 1无回表SQL 2发生回表一、什么是索引索引是帮助MySQL加快查询速度的排好序的数据结构。日常开发中我们常说“给这个字段加个索引”。但在 MySQL 的物理世界磁盘里索引绝对不是一个简单的“目录”而是一棵由数据页连接而成的庞大树形结构。二、MySQL索引数据结构的选择2.1. 为什么不用二叉查找树 / 红黑树二叉树BST如果插入的数据是有序的比如自增 ID 1, 2, 3, 4二叉树会严重退化成一个一字长蛇阵链表。此时查找时间复杂度退化为 O(N)跟全表扫描没区别。红黑树平衡二叉树虽然红黑树会通过旋转自动保持平衡查找时间复杂度是 O(log2N)但它致命的缺点是只有二叉。当数据量达到千万级时树的高度Height会非常高可能达到 20 多层。为什么高度致命在数据库中树的每一层都代表一次磁盘 I/O。机械硬盘或固态硬盘的 I/O 是极慢的毫秒级。查一条数据要扇形扫描磁盘 20 多次系统早就卡死了。2.2. 为什么不用哈希表HashHash 的优势根据 Key 精确查找某一行数据时时间复杂度是 O(1)快到飞起。Hash 的死穴无法进行范围查询Range Query。比如WHERE age 20Hash 索引就彻底抓瞎了因为哈希函数映射后的值是无序的它必须全表扫描。2.3. B 树B-Tree的妥协与痛点B 树是“多叉平衡查找树”它把二叉变成了“N叉”每个节点可以存多个数据大大压低了树的高度。但它有一个致命问题每个节点既要存索引的 Key又要存这一行的整行数据Data。计算机磁盘 I/O 的最小单位是页PageMySQL默认是 16KB。如果节点里塞满了大块的整行数据那么一个 16KB 的页能存的索引数量就非常有限。这意味着树还是会变高而且进行范围查询时需要频繁在父子节点间“上下横跳”做回溯效率很低。2.4. B 树MySQL 的选择B 树是 B 树的改良版它做出了两个决定性的改变非叶子节点不存 Data只存 Key索引值和指针。所有的完整数据Data全部挪到最底层的叶子节点。所有的叶子节点之间用双向链表首尾相连且是有序的。这带来的两个巨大优势出色的扇出Fan-out能力既然非叶子节点只存 Key 和指针大概占 10-14 字节那么一个 16KB 的页就能存下上百甚至上千个索引项。这意味着一棵高度仅为3 层的 B 树就能存储千万级的数据。你只需要 3 次磁盘 I/O 就能在两千万行数据里秒抓出你需要的那一行。天然支持范围查询比如查WHERE id BETWEEN 10 AND 50。B 树只需要先通过根节点往下定位到id10的叶子节点然后顺着叶子节点底部的双向链表一直往右扫直到看到id50停止。不需要再回溯到上层节点。BTree和BTree对比对比维度B-Tree (B树)BTree (B树 —— MySQL 的选择)数据Data存在哪所有节点根节点、中间节点、叶子节点全都有数据仅存在最底层的叶子节点中上层节点纯粹是导航用的 Key。单页16KB存储容量极小。因为行数据很胖一个页装不了几个 Key。极大。因为不存行数据一个页能装上千个 Key树变得极矮胖。范围查询Between灾难。必须在树的上下层级之间不断回溯、重复遍历。降维打击。只需要找到左边界直接沿着底部的链表向右顺序横扫。查询稳定性不稳定。运气好在根节点就找到了1次 I/O运气差在叶子节点才找到。绝对稳定。任何数据都必须走到最底层叶子节点每次查询 I/O 次数严格一致。三、 聚簇索引 vs 非聚簇索引在 InnoDB 引擎中根据叶子节点存储内容的不同索引被严格分为两类。1. 聚簇索引Clustered Index / 主键索引聚簇索引不是一种单独的索引类型而是一种数据存储方式。它的核心特征是索引的叶子节点就是真正的数据行本身。唯一性一张表有且只能有一个聚簇索引因为数据物理上只能按一种顺序存储。InnoDB 的主键选择策略如果你定义了PRIMARY KEYInnoDB 就用它做聚簇索引。如果没定义InnoDB 会找第一个非空的唯一索引Unique代替。如果连唯一索引都没有InnoDB 会在后台自动生成一个 6 字节的隐式自增列RowID来构建聚簇索引。2. 非聚簇索引Secondary Index / 辅助索引 / 二级索引日常我们自己通过CREATE INDEX创建的索引比如给age、name加索引全部都是二级索引。它的核心特征是索引的叶子节点存储的是索引列的值 对应的主键值。为了更直观地理解它们在物理存储上的结构对比图如下【 聚簇索引 (主键 id) 】 【 二级索引 (普通列 age) 】 [ Root ] [ Root ] / \ / \ [ Node ] [ Node ] [ Node ] [ Node ] / \ / \ / \ / \ [Leaf] [Leaf] [Leaf] [Leaf] [Leaf] [Leaf] | | | | | | ------- ------- ------- ------- ------- ------- | id1 | | id5 | | id10 | | age18| | age20| | age25| |nameA | |nameB | |nameC | | id5 | | id1 | | id10 | |age20 | |age18 | |age25 | ------- ------- ------- ------- ------- ------- (叶子节点只存索引列的值和主键id) (叶子节点包含整行数据的完整字段)四、 回表Lookup假设id是主键age是二级索引。我们执行以下两条 SQLSQL 1无回表SELECT id FROM users WHERE age 20;执行过程执行器请求 InnoDB 查age索引树在叶子节点找到了age20同时拿到它的对应主键id1。因为你只需要id二级索引树上已经有现成的了。专业术语这叫“覆盖索引Covering Index”效率极高不需要看聚簇索引一眼。SQL 2发生回表SELECT name FROM users WHERE age 20;执行过程执行器请求 InnoDB 查age索引树找到age20的节点拿到主键id1。发现你要拿name但二级索引树上没有name的数据。回表InnoDB 拿着id1这个钥匙转身去聚簇索引树主键树里重新查一次从根节点一路向下定位到id1的叶子节点从中取出nameA。把name返回给执行器。痛点这意味着你查一次数据走完了两棵独立的 B 树。如果查询结果有 1000 条可能就要执行 1000 次回表操作这正是很多 SQL 变慢的根源。
