数据库索引原理：从B+树到聚簇索引与实战优化

做数据库这行免不了被问一个问题索引到底为什么能加速查询我以前也是标准答案选手张口就是“B树、聚簇索引、最左前缀”可只要对方让我把B树画出来或者问一句“为什么不用链表”我就露馅。后来我换了种学法不再背结论而是从“数据在磁盘上怎么存、一条查询到底在做什么”开始推。推完发现那些看起来零散的索引知识点其实是一条线顺着走一遍就全通了。这套理解方式让我应付面试和线上问题都从容很多。下面我就按这条线把数据库索引原理用最简单的方式讲一遍。后面讲到 MySQL 和 InnoDB 会多一些但思路对大多数关系型数据库是通用的。如果你是刚入门不久的开发建议不要跳过前两节因为后面的“索引失效场景”和“建索引经验”全都要靠前面的原理撑起来。1. 索引为什么能省时间先回到数据是怎么存的1.1 没有索引的时候数据库在做什么一张表在磁盘上的最小读写单位通常是页InnoDB 里默认一个页 16KB一个页里放很多行记录。如果没有索引执行select * from orders where user_id 123时数据库并不知道 user_id123 的数据在哪个页只能从第一个数据页开始一页一页读进来在每页里逐行比对。这就是全表扫描复杂度 O(n)。数据量小的时候没什么感觉几百万行、上千个页的时候一次查询就要读大量磁盘慢就慢在这。这个行为很像一本没有目录的书。你想找某句话只能从头翻翻完一遍所有页面都过了一遍但你要的目标内容可能就一页。数据库里最直观的优化方向就是给这张表加一本“目录”也就是索引。目录本身也是一份额外存储的数据但它的体积远小于整张表查目录比翻正文快得多这笔投入是值得的。1.2 排序是“跳着找”的前提要打破全表扫描关键思路是先建立一份有序的“目录”。目录这一列按某种顺序排好找数据时先查目录而不是找正文。为什么强调有序因为有序之后才能“跳着找”。你查 50 这个数从中间开始比一次排除一半这就是二分查找复杂度从 O(n) 降到 O(log n)。但二分查找有个前提数组能用下标随机访问也就是能瞬间跳到中间位置。磁盘上散落的记录做不到这一点链表也不行因为链表要找到中间节点必须从头遍历。所以数据库不会直接对数据本身做二分而是构造一层额外的、有序的索引结构让查找可以在索引结构上快速跳跃再通过指针回到原始数据。这一点是理解 B树和哈希索引分道扬镳的起点后面所有内容都是围绕“怎么组织这份有序目录”展开的。1.3 数据库怎么把一张表变成可以跳跃查找的结构索引的物理形态就是“把某列的值抽出来排好序后面挂上指向对应记录的指针”。比如对 user_id 建索引等于单独维护一张按 user_id 排序的表每一项都写着“这个 user_id 的数据在原表的哪个位置”。查询的时候先在索引里快速定位再顺着指针去拿完整行。这就是索引的最小单元一个有序的键加一个指针。后面所有复杂概念B树、聚簇索引、二级索引本质上都是在回答“这个有序键和指针到底怎么组织才能读写都高效”。把这条主线抓住看到任何索引问题都可以先退回到这句话来想。比如“联合索引为什么有最左前缀”根源就是联合索引的有序性是先按第一个字段排的“覆盖索引为什么快”是因为它不需要拿着指针回原表取数据。满屏术语背后底层就是这句大白话。2. 从链表的痛点推出B树不背也能画出来2.1 为什么不能用一条链表撑起索引如果你已经知道索引等于“有序键加指针”那最简单的方式就是把键串成一条有序链表。链表插入和删除都很方便改几个指针就行但查找很难受。有序链表只能从头节点开始一个节点一个节点走没法直接跳到中间因为要跳到中间必须知道中间节点的地址可链表是按指针一个连一个的中间节点没有“下标”。这意味着链表上的查找还是 O(n)没有解决根本问题。那怎么办解决思路这时候就出来了既然一条链表跳不了就多建几层更稀疏的链表用上层链表做跳跃这就是多级索引链表也叫跳表。这个概念在面试里偶尔会出现但很多人只记住了名字没记住它是为了解决“链表不能二分”这个问题才出现的。2.2 多级索引链表跳表思想跳表的做法很朴素底层是完整的有序链表每隔几个节点提取一个节点到上一层上一层再每隔几个节点提取到更上一层。查一个值时先从最高层开始找发现目标落在某个区间就降到下一层继续每层都能跳过一段节点。平均查找复杂度能做到 O(log n)而且实现比平衡树简单Redis 的有序集合底层就用了跳表。数据库的磁盘环境和内存不同跳表的指针跳跃比较频繁对磁盘不友好但它给了我们一个非常重要的方向一个有序结构想快就是让查找路径变短让一次比较能跳过尽量多的数据。B树做的就是这件事只是把“跳表”的层级组织方式换成了更紧凑的树形目录。换句话说B树不是凭空冒出来的它是“有序链表 多级索引”思想在磁盘环境下的落地版本。2.3 B树的形态目录套目录叶子串成链B树的形态可以理解成“多层目录”。最上面一个根节点下面一层是内部节点最底层是叶子节点。叶子节点里放着真正有用的东西索引键加指向数据的指针。内部节点不存数据只存键和指向下一层的指针用来做路由。所有叶子节点之间用双向链表串起来这是为了范围查询方便找到第一个符合条件的叶子后顺着链表往后走就行不用再回头爬树。为什么这种结构适合磁盘因为磁盘 IO 是按页读的一次读一个页。如果树每层只有一两个节点那查一次要访问的层数就多IO 次数多。B树每个节点就是一个页页大小 16KB里面能塞几百上千个键所以一棵两千万行的表B树高度通常也就三四层。一次索引查询读三四次页就能定位到数据这就是它快的原因。2.4 为什么选B树而不是二叉树或哈希面试里经常问“为什么不是红黑树”和“为什么不是哈希”。红黑树是二叉树每个节点只能放一个键数据量大时树非常高查询十几层的节点每层一次磁盘 IO扛不住。B树的每个节点是一个页一个页放一堆键树变得又矮又宽磁盘 IO 次数从十几降到了三四次。B树和B树的区别在于B树的内部节点也会存数据导致一个页能放的键变少树更高B树内部节点只存键叶子才存数据所以同样的页大小B树能塞更多路由信息。再加上叶子节点的链表让范围查询变得非常自然B树就胜出了。哈希我们后面单独讲它擅长精确匹配但不擅长排序和范围和 B树各有各的战场。3. 主键索引和二级索引一棵树上走了两条路3.1 聚簇索引主键就是数据本身的门牌号在 InnoDB 里表是按主键聚簇存储的聚簇的意思就是数据行本身按照主键的顺序物理组织。主键索引的叶子节点不是指针而是完整的一行数据。所以你查主键等于直接走到数据页里把行拿到不需要二次跳转。这带来一个直觉建表时一定要有主键。InnoDB 里如果你没指定主键它会偷偷找一个非空唯一列当主键实在没有就生成一个隐藏的 rowid 当主键反正聚簇索引一定存在。主键的顺序就是数据页里的物理顺序这个特性会直接影响后面的插入性能。很多人以为主键只是用来唯一标识一行但从存储角度看它更重要的身份是聚簇索引的排序键。3.2 二级索引先找到主键再回表取数据除了主键索引你建的其它索引都是二级索引也叫非聚簇索引。二级索引的叶子节点不存整行只存“索引键 主键值”。比如你在 user_id 上建索引索引里每个键后面挂的是对应的主键 id。当查询条件用到 user_id 时MySQL 先在二级索引树上找到主键 id再用主键 id 回聚簇索引树查一次才能拿到完整行。这一步就是“回表”。回表多一次 B 树搜索虽然很快但比“直接在聚簇索引上拿数据”慢。这也是为什么不要动不动就select *宽表回表的代价更明显。认识这条链路后面的覆盖索引优化就顺理成章了。很多时候优化 SQL 不是让查询不走索引而是让查询少回表或者干脆不回表。3.3 覆盖索引省掉回表的关键一招如果查询需要返回的列全部存在于某一个二级索引里MySQL 就不需要再回表了。比如表里有联合索引(user_id, status)执行select user_id, status from orders where user_id 123索引里已经包含这两个字段直接遍历二级索引叶子节点就能返回结果explain 的 Extra 列会显示Using index。这个就叫覆盖索引。覆盖索引不是一种独立的索引类型而是一种“查询命中了索引的全部所需列”的状态。实际调优里它是省回表最有效的手段。经常见的做法是把高频查询里需要的字段加到联合索引后面但加的字段也别太多因为每个索引都有存储和写入成本。一个常见误区是明明只查两三个字段却习惯性写select *把覆盖索引的优势白白浪费掉。3.4 为什么在线业务都强调主键用自增因为聚簇索引的数据行是按主键顺序物理排列的。插入一条自增主键记录时新记录总是在最后面InnoDB 只需要追加很少触发页分裂。如果用 UUID 或随机字符串做主键新记录的主键随机落在已有区间中间为了维持聚簇顺序数据库可能要把某个页拆成两个新页挪动一半的数据写放大严重还会产生页碎片。这只是主键设计的一个考虑点不是绝对的。分布式的场景里全局严格自增 id 往往不可行那就用雪花算法之类的主键再尽量顺序生成。重点是理解了聚簇索引的物理组织方式后你就能自己权衡而不是死记“主键必须自增”。如果有人问你为什么你可以从页分裂、物理顺序、随机写这几个词展开讲而不是只扔结论。4. 哈希索引和B树索引两种存储路线4.1 哈希索引为什么快算一次就知道在哪哈希索引的思路不一样它不对键做排序而是用一个哈希函数把键值换算成一个固定长度的数字再通过这个数字直接定位到对应的槽位。等值查询where id 100只要算一次哈希然后去槽位里找理论上复杂度是 O(1)比 B 树的 O(log n) 还快。这就像一个仓库管理员拿着编号牌每个编号对应一个固定货架不用翻目录直接走去拿。这种结构下内存数据库或者缓存里大量使用哈希结构。像 Redis 的 dict、Java 的 HashMap都在用这个思路。但把它直接应用到磁盘关系型数据库的通用索引上问题就来了因为数据库的查询场景远不止等值匹配。4.2 哈希的短板范围、排序、前缀匹配全都靠边哈希函数的结果是散乱的排序被破坏。查询where age 20时你无法用哈希索引判断“大于20的键在哪些槽里”因为哈希后的位置和原始大小完全没有关系所以哈希索引天然不支持范围查询、排序、模糊前缀匹配。另外哈希冲突后还要处理冲突链某一段数据特别多的时候哈希退化成链表性能也不稳定。数据库里如果只有哈希索引那很多常规 SQL 都没法用索引了。这也是为什么主流数据库的默认索引是 B树哈希更多用在特殊的等值场景比如 Memory 引擎的表或者某些 NoSQL 的主键访问。设计存储结构时本质是在“等值查询快”和“范围查询快”之间做取舍没有哪种结构是万能的。4.3 InnoDB里的哈希自适应哈希索引InnoDB 里有一个和哈希相关的概念叫自适应哈希索引它不是 DBA 手动创建的而是 InnoDB 在运行时观察如果某个索引值的等值查询非常频繁它就可能自动在 B树之上建立一层哈希索引让这些热点查询直接用哈希定位减少 B树的层数访问。这个机制对应用完全透明也说明 B树和哈希不是一定要二选一可以组合使用。你从业务侧无法直接指定“给我加一个自适应哈希索引”但可以通过让某类等值查询更集中来让它更容易被触发。理解原理后遇到 Memory 表、Redis 等场景你就能判断该用哈希结构还是有序结构而不是拿到任何数据都只想到建 B树。5. 索引失效场景知道原理后不用背八股5.1 最左前缀联合索引的排序契约联合索引(a, b, c)不是把三个字段分别排序而是先按 a 排序a 相同再按 bb 相同再按 c。这相当于一本先按拼音首字母、再按第二个字母、再按第三个字母排序的字典。查询如果只给 b 不给 a就等于想按“第二个字母”查字典整本字典的有序性在这层上是不可用的所以无法走索引。这就是最左前缀原则的根。面试题总爱问“联合索引 (a,b,c)查询条件是 b1 和 c2 能不能走索引”答案通常是走不了因为没带 a索引的有序链就从中间断裂了。如果带了 a 但缺 b只能用到 a 这一列的范围过滤c 用不上。这些都不用背画一下联合索引的排序方式就通了。5.2 函数、运算、隐式类型转换破坏排序稳定性B树能快速查找依赖“键本身有序”。可一旦你对索引列做了函数或运算比如where DATE(create_time) 2024-01-01数据库必须先对每一行的 create_time 算一遍函数才能拿结果和右边的值比较原来的索引键顺序已经不能直接用了索引自然失效。解决办法是改写为where create_time 2024-01-01 and create_time 2024-01-02。这里的原则是把对列的计算改成对常量的计算。隐式类型转换也是同一类问题。当索引列是 varchar你写where phone 13812345678MySQL 会尝试把字符串列转成数字再比较等于在索引列上套了一层转换同样破坏有序性。反过来说如果索引列是数字你传字符串是常量在转换索引通常还能用。判断方法就一条看被套上函数或转换的是不是索引列本身。5.3 like、or、not in优化器为什么不选索引like abc%能走索引因为前缀是确定的可以像查字典一样先定位到 abc 开头的位置然后顺着链表往后扫。like %abc就不行因为开头未知你无法告诉 B树“从哪开始找”只能全量扫描这和字典查字一模一样知道首字母才能翻页。or的情况要复杂一点or 两边字段都有索引时MySQL 有可能用 index merge 合并两个索引的结果但如果没有合适的索引就会退化成全表扫描。not in通常难用索引因为它是在“取反”B树擅长找一条路径不擅长排除大量值。理解这些现象背后的原因比背一个“失效场景清单”可靠得多因为优化器版本在变场景也在变。5.4 把“失效”归成两类一张表记住把所有常见失效场景放一起看本质只有两类一类是查询条件破坏了索引键本身的有序性另一类是优化器统计后认为全表扫描比走索引更便宜。第二类常见于表很小、返回行数占比很高、索引区分度太低这些情况。区分度低意味着走索引要回表很多次可能还不如顺序扫描。场景失效根因本质联合索引缺最左列无法利用排序前缀破坏有序性对索引列用函数/运算排序键被改写破坏有序性隐式类型转换索引列被隐式转换破坏有序性like %xx起始位置无法确定无法二分定位or 分支无索引只能部分走索引回表过多优化器选全表not in / 数据占比大返回行过多优化器选全表提示判断一个 SQL 能不能走索引别背口诀。用 explain 看 type、key、rows、Extra再对着这条 SQL 想想“索引键的有序性有没有被破坏”基本就准了。6. 现实中设计索引几条直接能用的经验6.1 区分度优先不要见字段就建索引不是越多越好。每个索引都要占磁盘写入时要同步维护删除和更新也要改索引。区分度太低的字段比如性别、状态枚举值就算建了索引优化器也经常弃用因为一分钱收益没有还拖慢写入。判断区分度可以跑select count(distinct col)/count(*) from table数值越接近 1区分度越好。不过区分度也不是唯一标准联合索引里还会把高频、等值查询的字段放前面后面再接区分度不错的字段。设计索引的第一原则是从真实慢查询出发不要拍脑袋给所有字段建索引。我曾经见过一张表建了十几个索引写入慢得离谱结果排查下来真正高频使用的就三个。6.2 联合索引的字段顺序怎么排字段顺序按“等值条件优先、范围条件靠后”来排。等值条件比如a 1 and b 2两个字段放在前面都能定位范围条件比如create_time between ...它只能过滤一段如果能把它放到后面前面的等值字段可以先把数据缩到很小。另一个思路是考虑索引复用联合索引(a, b)能覆盖单独查 a 的场景但单独查 b 用不上所以把高频查询字段放左边通常不亏。也要注意别为了追求“覆盖更多查询”把联合索引搞太长每个字段都增加一层排序索引叶子变大一个页能放的行变少性能反而下滑。一般三到五个字段以内的联合索引比较常见。索引设计的核心是解决实际慢查询而不是把所有可能的查询组合都预先覆盖一遍。6.3 慢查询日志和 explain 是索引设计的地图我自己调优的第一步永远是开慢查询日志把执行时间超过阈值的 SQL 捞出来然后对每一条跑 explain。explain 里重点看几个地方type 是不是 index/range/ref/constkey 有没有用到目标索引rows 估算扫了多少行Extra 里有没有 Using filesort、Using temporary。比如typeALL表示全表扫描rows很大就要找合适的索引。ExtraUsing filesort说明排序没走索引如果排序字段正好在一个未用到的索引里可以考虑调整查询让排序走索引。把这两样配合起来比任何“默认优化”都更能说明问题。很多性能问题不是 SQL 语法不对而是索引没能支撑查询路径explain 能很直观地暴露这一点。6.4 一个实际例子从查不快到压到毫秒级之前遇到一个订单表的慢查询业务侧说偶尔一次查询要几百毫秒。SQL 大概长这样select id, order_no, status, create_time from orders where user_id ? and status ? and create_time ? order by create_time desc limit 20;表里已经有 user_id 单列索引但 status 和 create_time 过滤后还要回表排序数据量大时很慢。最后建了一个联合索引(user_id, status, create_time)等值条件放前面范围排序字段放最后。查询扫描行数从几万降到了几十延迟从几百毫秒降到个位数毫秒。这个调整没有用任何花哨技巧就是把前面的原理落到 SQL 上等值先缩范围范围字段做排序避免 filesort。我自己现在遇到任何索引问题都不先背结论而是先问一句查询要在哪棵树上找树上每个节点的键是有序的吗如果有序性被破坏再看优化器有没有更便宜的路径。这个习惯帮我处理过不少线上慢 SQL也帮我面试时把“索引失效”这类问题讲得很有底气。这套理解方式推起来不快但推过一遍之后就不容易忘。你下次遇到一个索引相关的怪问题也可以试着先别急着搜答案画一画索引的树形结构答案大概率会自己冒出来。