做后台这一行久了你会发现很多性能问题最后都指向同一件事系统在大量重复做无效比较和无效扫描。运营同事翻到订单列表第 200 页时接口卡顿不是索引失效而是 MySQL 在 LIMIT 深度翻页时白白扫描了二十万行程序里做排序输出排行榜复杂度看着没毛病实际比较次数翻了十几倍甚至看论文时发现连数据库索引都在想方设法让字符串比较不要每次都从头逐字节来。这篇是 DARTS 系列的第一篇我集中整理三块内容Tournament Sort 算法、MySQL 深度翻页优化技巧、ByteSlice 论文的精读笔记。三件事表面不相关底层思路却能串成一条线适合后端开发、DBA、以及想系统补排序和索引知识的同学参考。1. Tournament Sort 算法把“比赛结果”存下来下一轮直接用1.1 从选择排序说起被丢弃的比较结果太可惜了先回忆一下最简单的选择排序。给你一个长度为 n 的数组每次找出最小值放到结果数组里然后继续找剩下元素的最小值。每次找最小值都要扫一遍剩余元素比较次数是 n-1、n-2、n-3……最后总量是 O(n^2)。问题很明显第一轮你明明比较了很多对元素知道“a 比 b 小、b 比 c 小”但第二轮重新找最小值时这些信息全部作废又从头比较了一遍。这就像一场淘汰赛打完了你知道冠军是谁却非要重新把所有选手再安排一次比赛才能知道亚军是谁完全不利用上一轮的战绩。Tournament Sort 的思路正是来自体育比赛把所有待排序元素当成参赛选手两两一组比赛胜者进入下一轮。下一轮仍然是两两比赛直到选出全场冠军。然后把这个“冠军”从比赛里移除此时不需要让所有人重新打一遍只需要沿着冠军之前走过的比赛路径把胜者补上来就可以再经过 log 层比较新一任冠军就产生了。这种思路也叫胜者树核心收益是每一轮产生最小值时比较次数从 O(n) 降到 O(log n)整体排序时间复杂度从 O(n^2) 降到 O(n log n)。举个例子数组 [5, 3, 8, 1, 9, 2, 7, 4]第一轮可以组成如下胜者树。[3] / \ [1] [5] / \ / \ [3] [0] [5] [6] / \ / \ / \ / \ 5 3 8 1 9 2 7 4每个叶子节点是数组元素内部节点保存的是两个子节点中“较小者”的下标。根节点 [3] 表示下标 3 的元素是 1即整个数组最小值。取出 1 之后把下标 3 这个叶子位置标记为已淘汰然后从它的父节点开始向上重新比较只要走这一条路径根节点很快就会更新成 2。每一轮更新只涉及树的高度所以单次提取最值的成本是 O(log n)。1.2 胜者树实现与复杂度细节为了把流程说清楚我写了一个基于数组的胜者树版本。这里的实现不是追求极致性能而是把算法结构表达清楚面试和工程改造时可以参考。def tournament_sort(arr): n len(arr) size 1 while size n: size 1 # 扩到 2 的幂方便用完全二叉树表示 tree [None] * (2 * size) def winner(i, j): # 返回胜利者的下标None 表示这个位置没有有效选手 if i is None: return j if j is None: return i # 相等时选下标小的保证排序结果稳定可预期 return i if arr[i] arr[j] else j # 初始化叶子节点前 n 个是真实元素后面补 None 哨兵 for k in range(size): tree[size k] k if k n else None # 自底向上建树 for k in range(size - 1, 0, -1): tree[k] winner(tree[2 * k], tree[2 * k 1]) result [] for _ in range(n): cur tree[1] # 根节点就是当前最小值下标 result.append(arr[cur]) # 把这位冠军从叶子节点处移除 p size cur tree[p] None # 沿路径向上更新 p // 2 while p: tree[p] winner(tree[2 * p], tree[2 * p 1]) p // 2 return result建树阶段把所有两两比较做一遍复杂度 O(n)。每取出一个最小值从叶子到根更新路径长度为树高也就是 O(log n)总共取出 n 个元素所以整体时间复杂度 O(n log n)。空间上叶子数被扩充到 2 的幂所以辅助数组约 2 倍容量理论上空间复杂度 O(n)但实际比“原数组加结果数组”这种实现更费内存。一个容易被忽略的点稳定性。如果两个元素值相同谁先被选出来会影响最终顺序。我在 winner 函数里用下标做 tie-breaker让排序结果稳定。工程上批量排序时稳定排序的意义在于多次排序的复合结果可预期比如先按时间排再按状态排状态相同时仍能保持时间顺序。1.3 堆排序与败者树同族兄弟各有分工理解了胜者树再看堆排序就非常顺。堆排序其实是把胜者树“压扁”到一个数组里用下标关系隐含父子节点省掉了指针和额外树结构再通过上浮/下沉操作动态维护序关系。两者思想同源只是工程形态不同。堆排序在内存里能做到原地排序空间复杂度 O(1)所以日常排序教科书写得更多而胜者树更适合描述“多路归并”场景。在数据库和外部大文件排序里更常见的其实是败者树。它和胜者树的最大区别是内部节点记录的是“失败者”根节点额外记录当前胜者。每轮淘汰掉冠军后新选手只需要沿着路径和各个内部节点中记录的败者比较不需要额外判断“这个节点原来是不是冠军”更新路径上的分支判断更少性能更好。说白了一点胜者树每次都要重新“确认”胜者败者树只记录输家冠军更新逻辑更直接。很多外部排序框架和数据库归并排序都采用败者树做 K 路归并这是 Tournament Sort 真正最实用的落地点。不过我得说句实在话如果你只是写业务代码要对一个几万行数组排序直接用语言自带的排序函数不要手写这个算法。Tournament Sort 的学习价值在于理解比较复用思想和外部排序原理真正的工程价值在数据库执行引擎和复杂归并场景里不在 CRUD 项目里。2. MySQL 深度翻页为什么慢以及三种立竿见影的优化思路2.1 慢的本质LIMIT offset 是“扫描加丢弃”不是跳转先看一条典型的深分页慢查询。SELECT id, order_no, create_time FROM order_info WHERE status 1 ORDER BY create_time DESC LIMIT 200000, 20;这条 SQL 的语义是“跳过前 20 万条返回第 200001 到第 200020 条”。MySQL 处理 LIMIT offset, size 时会从索引或表里读取 offset size 行然后丢弃前 offset 行。你以为翻到了第 20 万条附近实际数据库读了 200020 行只为返回最后 20 行。如果 ORDER BY 字段没有索引更惨要先 filesort 把结果在临时文件里排好序再从排序结果里取第 200001 行排序的代价是全表数据量而不是 20 万行。更隐蔽的问题是随机 IO。InnoDB 的聚簇索引叶子节点存整行数据走二级索引排序时每读到一条记录通常还要回表取一次完整行。深翻页时回表次数等于 offset size 次20 万次随机主键查找哪怕每次只要 0.1 毫秒累积下来也是十几秒起步。这就是为什么“翻到第 10 页还很快翻到第 200 页直接超时”。2.2 方案一延迟关联让分页先走覆盖索引延迟关联的核心思路是不要一开始就拿完整行先在一个覆盖索引里完成排序和定位拿到这一页真实需要的主键 ID再用这几十个 ID 回去取完整数据。因为覆盖索引里没有回表动作MySQL 只需要在索引页之间顺序扫描并丢弃无用行开销小很多。SELECT t.id, t.order_no, t.create_time FROM order_info t INNER JOIN ( SELECT id FROM order_info WHERE status 1 ORDER BY create_time DESC, id DESC LIMIT 200000, 20 ) AS page ON t.id page.id ORDER BY t.create_time DESC, t.id DESC;内层子查询只查 id排序字段 create_time 如果和 id 一起建立在联合索引里整个过程都可以在索引上完成不需要回表。拿到 20 个 id 之后外层再 join 回原表回表次数只有 20 次。相比原查询少了 20 万次回表效果通常立竿见影。我实战中用过这个方案把一条原本 1.8 秒的深度翻页查询压到 200 毫秒左右。不过要提醒一句MySQL 优化器对外层 JOIN 结果的输出顺序并不保证所以外层依然要显式 ORDER BY否则可能出现“这一页数据内容对但顺序乱了”的诡异问题。外层排序只对 20 行进行代价几乎可以忽略。延迟关联还有一个变体直接把完整结果先放在临时表或业务层然后用主键 IN 查询。本质上思路一样都是把“定位页码”和“取数据”两件事件分开处理。2.3 方案二键集分页参数带上游标位置延迟关联确实能优化深翻页但 offset 到 20 万时还需要扫 20 万行索引记录性能虽然比回表好很多却不是恒定最优。如果业务场景是“下拉加载更多”“朋友圈式流式刷新”可以考虑键集分页也叫游标分页或 Seek Method。核心思想很朴素记住上一页最后一行数据的位置下一页查询用位置条件过滤而不是用页码计算 offset。-- 上一页最后一条记录为 (create_time, id) (2024-11-30 10:00:00, 1024) SELECT id, order_no, create_time FROM order_info WHERE status 1 AND ( create_time 2024-11-30 10:00:00 OR (create_time 2024-11-30 10:00:00 AND id 1024) ) ORDER BY create_time DESC, id DESC LIMIT 20;这种查询的本质是从索引的某个具体位置开始往后扫数据库中并没有“跳过 20 万条记录”的额外动作。条件里的 id 是作为排序并列键的 tie-breaker保证多行 create_time 相同时能稳定排序否则可能出现记录被漏掉或重复返回。要发挥键集分页的威力索引设计很关键通常建议建联合索引ALTER TABLE order_info ADD INDEX idx_status_ct_id (status, create_time, id);这样 WHERE 条件里的 status 等值匹配使用索引第一列create_time 和 id 既用于范围定位也用于排序Extra 里不会出现 filesort。如果场景更简单比如只按自增主键倒序取数据SQL 可以简化成SELECT id, order_no, create_time FROM order_info WHERE id 1024 ORDER BY id DESC LIMIT 20;这个方案性能非常稳定不管加载到第几页扫描行数始终约等于每页大小。缺点也直接不能跳页。产品经理如果死活要求“用户能直接跳到第 1000 页”这个方案就没法用。在实际项目里我都会先和产品确认这个列表是后台分批加载还是用户主动搜索如果是移动端信息流基本都会接受“加载更多”的交互深翻页问题直接就没了。2.4 方案三业务层覆盖深度限制和缓存兜底有些管理系统必须有页码跳转比如“跳转到第 300 页”那优化空间就非常有限。这时候与其死磕 SQL不如在业务层做限制。一种常见做法是最大翻页深度限制。后台列表只允许翻到前 100 页超过限制就提示用户缩小时间范围或增加筛选条件。本质是承认数据库不适合无限深分页用产品规则规避痛点。另一种是对热点页做缓存。比如前 10 页数据可以放进 Redis页面换来换去都命中缓存。不过缓存只适合低频更新数据订单这类实时数据不太合适。如果确实要无限制跳页十年以上的大表得考虑更重的方案比如按时间分表、冷热分离、或者把明细数据导入搜索引擎/数仓让数据库专门负责细节回查。这些已经不是一条 SQL 能解决的问题而是数据架构问题。2.5 四种方案对比与执行计划检查分页方案适用场景优点缺点普通 LIMIT offset数据量小、翻页不深实现简单深度翻页回表多、扫描量大延迟关联后台分页、可跳页大幅减少回表次数深 offset 仍需扫描索引记录键集分页App 加载更多、流式列表性能恒定几乎不受页深影响不能跳页需改交互业务层限制/缓存必须页码跳转但有深度阈值彻底避免深翻页产品上有限制需要协调优化之后务必用 EXPLAIN 看执行计划重点看三处。一是 type理想情况至少是 ref 或 range尽量避免 ALL 全表扫描二是 key确认实际用到了预期的联合索引三是 Extra出现 Using filesort 或 Using temporary 就要警惕。注意 EXPLAIN 里的 rows 只是估算值最终性能建议用 profiling 或 performance_schema 看真实耗时尤其深分页场景估算值和实际可能差一个数量级。3. 论文 ByteSlice Review字节切片索引到底在加速什么3.1 先交代背景字符串比较是索引里最容易忽视的成本做数据库内核和应用索引优化的人都知道字符串查询的瓶颈往往不在“找了多少行”而在“比较每个字符串花了多久”。以 B 树为例每下降一层都要拿查询 key 和节点里的多个 key 做比较字符串从第一个字节开始逐字节比较公共前缀越长平均比较的字节数就越多。数据量到千万级后这种比较还伴随着随机内存访问CPU 缓存命中率低时间都耗在等待内存数据上。这是 ByteSlice 这篇论文吸引我的原因。论文围绕一个很工程化的思路展开把一个字符串 key 按字节切片让查询不再是“一次性完整串比较”而是“先做多级小范围的位并行过滤”。我在这里按论文公开思路和个人理解做 review不代表作者实现细节重点讲清技术路线和它的工程价值。3.2 ByteSlice 的核心思路把一串比较拆成一堆可并行的小比较论文的核心设计可以理解为三步。第一步预处理阶段把变长字符串 key 切成若干定长字节片。比如一个邮箱地址 “bobexample.com”可以切成每 8 字节一片的切片序列。第二步为每个切片单独建索引索引项定长存储。这一步非常关键定长意味着可以使用 SIMD 或位运算做批量比较不用像传统 B 树那样逐字节循环。第三步查询阶段先拿第一个切片过滤候选集合。由于第一片往往能筛掉大部分不匹配项命中集合迅速缩小然后再拿第二片、第三片逐级过滤最后只剩下极少数候选者才做完整字符串比较。这个思路和数据库里的位切片索引是一脉相承的。位切片索引把数值的每一个 bit 单独拿出来建位图查询时用逻辑运算快速定位满足范围条件的记录。ByteSlice 把这种思路推广到字符串场景把字符串按字节切片本质是让“比较”这个操作尽可能向量化和并行化减少直接比较长字符串带来的慢速路径。3.3 优势、代价与适用边界ByteSlice 这种方案在几个场景下确实很漂亮。一是缓存友好定长切片可以数据对齐SIMD 指令一次处理多个字节吞吐量比逐字节比较高很多。二是适合前缀区分度高的数据比如用户名、订单号、日志 traceId开头几位就能筛掉绝大多数记录。三是比较过程天然可并行多个切片过滤任务可以分给不同线程能利用多核 CPU。但代价也不小。最直观的是索引膨胀。一个 32 字节的 key切成 4 片每片都可能产生独立索引项索引空间很可能翻几倍。写入时更麻烦插入一条记录要同步更新多层切片索引写入路径变重删除操作也要处理多个切片的清理。因此它更适合读多写少、key 长度差异大、查询模式集中在等值和前缀匹配的数据集比如对象存储元数据索引、日志归档查询这类场景。另外它对数据分布非常敏感。如果前缀重复率极高比如所有记录都以 “user_” 开头那么第一片、第二片过滤能力都很弱查询仍要深入比较很多层效率优势会明显打折扣。甚至有可能在构建多层索引后实际过滤收益还不如一次完整字符串比较来得快。3.4 这篇论文给我的横向联想一切优化都是减少无效数据搬运读完 ByteSlice 之后我立刻联想到两个东西一个是布隆过滤器一个是列式存储里的 zone map。布隆过滤器能快速说“肯定不存在”目的是减少无效 IOByteSlice 则是在比较阶段做减负。列式存储的 zone map 在每个数据块记录最小值、最大值查询时先跳过不可能命中的块和 ByteSlice 的逐级过滤思想也很像。它们都在解决同一个问题不能让大量数据在无关比较中白白消耗资源。这和前面两段内容其实是同一条主线。Tournament Sort 把比较结果缓存起来避免下一轮重复比较MySQL 深翻页优化通过覆盖索引和游标定位避免重复扫描大量无辜行ByteSlice 通过字节切片和多级过滤避免完整字符串比较。本质都是想少做点事。4. 实操中绕不开的几个坑与排查建议4.1 排序算法落地时的踩坑记录我见过不止一次有人出于“学习算法”的目的在业务项目里手写 Tournament Sort 或堆排序结果效果反而不如系统自带的排序函数。原因是现代语言运行时自带的排序实现比如标准库里的内省排序或 Timsort会针对不同数据量选策略还能利用 CPU 缓存代码在通用场景下优化得很极致。手写算法除非你深入调优否则很难赢。正确姿势是面试时搞懂原理写框架或中间件时按需改造归并排序业务代码里尽量用内建函数。如果真的要在组件里实现胜者树或败者树别忽略三点。一要处理哨兵节点数组长度不是 2 的幂时补齐的节点要设计为空值不能放任脏数据参与比较。二要在值相等时定义清楚选谁否则排序不稳定日志排查时你会看到莫名其妙的前后顺序变化。三要评估空间开销胜者树辅助空间接近原数组两倍数据量大的时候内存消耗要提前估算。4.2 MySQL 翻页优化的易错点每一个我都踩过延迟关联写完忘记外层 ORDER BY是最容易犯的错误。内层子查询结果顺序不能代表外层 JOIN 结果的顺序不显式排序就会乱用户刷新页面看到上一页和下一页顺序不一致会直接反馈“数据错乱”。排查时不会马上想到是排序缺失可能会先怀疑并发写入浪费时间。键集分页的成功完全依赖排序键有索引。有一次我用 create_time 做游标但表里只有单列索引 status没有联合索引SQL 执行时还是 filesort结果比之前的延迟关联还慢。后来建了 (status, create_time, id) 联合索引性能才真正稳定。所以用这个方案前第一件事不是写 SQL而是看索引设计。还必须注意 NULL 值。ORDER BY create_time DESC 时create_time 为 NULL 的行在 MySQL 默认排序规则里会出现在结果的最前面还是最后面不同版本和不同排序方向可能有差异。用游标分页时如果上一页最后一条是 NULL 值下一页的create_time ?条件无法正确匹配到 NULL就会出现漏数据。稳妥做法是业务上约定 create_time 不允许为 NULL或者用 COALESCE 给一个默认值并让排序键保持一致。4.3 索引类优化的重要提醒做索引优化时常见误区是“看执行计划没问题就收工”。EXPLAIN 是估算模型深分页场景的 rows 经常不准一定要结合实际执行时间、状态变量 handler_read_next、handler_read_rnd_next 判断真实读了多少行。另外联合索引的字段顺序不能随便排要把等值条件的字段放前面范围排序字段放后面否则无法完全走索引下推。还有一句话必须放在前面索引不是免费的。每多一个索引写入时都要同步更新对应的 B 树写多读少的表加索引前一定要评估写放大。ByteSlice 这类切片索引也一样读性能提升背后是写入路径和多倍存储成本的增加落地前至少要在目标数据集上做小规模压测看一下索引构建耗时、空间膨胀率、以及数据倾斜情况下过滤率到底能到多少。4.4 问题排查与方案选型速查表问题场景典型现象推荐排查思路推荐方案自定义排序慢大数据量排序耗时高确认是否真的需要全局有序检查算法时间复杂度优先内建排序外部排序用败者树多路归并深翻页慢LIMIT 200000 后响应数秒EXPLAIN 看 type、rows、Extra观察回表次数延迟关联或键集分页翻页结果乱序每页数据重复或缺失检查排序键是否唯一检查外层 ORDER BY排序键加 id 做 tie-breaker补全 ORDER BY游标分页无效新方案和旧 SQL 一样慢检查联合索引是否真的覆盖排序键建 (等值字段, 排序字段, id) 联合索引索引空间膨胀磁盘占用显著上升统计索引大小和写入 TPS评估冷热分离、减少冗余索引或放弃部分方案我在实际排查这一类问题时的体会是带宽和 CPU 往往不是瓶颈真正吃掉时间的是无效数据搬运。一次深翻页卡顿背后是二十万次回表一次排序慢背后是大量重复比较一次索引查不准背后是每个字符串都在从头比到尾。所以拿到性能问题先问一句“系统这次为了返回一点点结果到底搬了多少数据”思路基本就打开了。希望对你有帮助。