企业官网建设流程全解析

DARTS#01这期，我把三个看起来很散的词凑到了一起：Tournament Sort算法、MySQL深度翻页优化、字节切片编码论文ByteSlice。如果你只是被其中一个词吸引点进来，我也建议把另外几节扫完，因为它们其实是同一根技术主线上的三段：基础算法决定你对排序的直觉，SQL改写解决你手头的线上问题，论文则给你往后看两三年的视野。这是DARTS系列的第一篇，后面会沿用这种“一道算法、一个工程优化、一篇论文速读”的格式。

1. 为什么把排序算法、翻页优化和一篇论文放在同一期

1.1 DARTS的定位和选题逻辑

做这个系列的初衷很简单：我发现很多做后端开发和数据库维护的人，知识结构往往是“点状”的——懂索引、懂EXPLAIN、懂几条优化SQL，但碰上复杂问题还是很难串成一条线。今天这条线是“数据如何被排序、如何被翻页、如何被压缩存储”。

三个看似无关的话题，其实都指向数据库吃不消时的典型场景。排序算法是数据库执行计划的地基，MySQL的filesort和外部归并都建立在树形比较结构上；深度翻页是OLTP系统最常见的性能杀手，一条只取20行的查询能把机器拖到IO瓶颈；ByteSlice则是OLAP列式存储里的编码思路，让你理解列存为什么能在海量数据上跑得比行存快一个数量级。

1.2 三个关键词之间的隐藏主线

我先说一个自己的体会：调优MySQL查询，从来不是背几条SQL写法就能解决的。你得先弄清楚数据库在执行这条SQL时，把数据从磁盘搬进内存后做了什么。

Tournament Sort是“怎么用最少的比较找出最小值”的算法答案；深度翻页优化是“怎么让数据库少做无用功”的工程答案；ByteSlice是“怎么让数据在磁盘上占更少空间、扫描时读更少字节”的存储答案。三条答案放在一起，才是一份完整的性能优化认知框架。

1.3 适合谁来读这篇文章

如果你是后端开发，建议重点看第3章和第4章，里面是可落地的SQL改写方案；如果你是准备面试的候选人，第2章的算法推导和第5章的论文拆解可以给你提供不错的谈资；如果你已经在维护千万级数据表，那第3章的量化分析可能能解释你上周遇到的那次慢查询。整体阅读大概需要15分钟，代码可以直接抄。

2. Tournament Sort：树形选择排序如何点亮外部归并

2.1 从简单选择排序到锦标赛：为什么要两两对战

先回忆一下最简单的选择排序：每次线性扫描整个数组找到最小值，把它放到结果数组里，下次再扫描剩余部分。这个算法的问题很明显——找第k个最小值时，前面比较过的信息全部丢弃，下次又要从头比一遍。n个元素找最小，平均要比较n/2次；找n个最小值，总比较量就变成O(n²)。

Tournament Sort的思路是：既然要反复找最小值，那把每一轮比较的“胜者”记录下来，避免重复劳动。这就像世界杯淘汰赛，32支球队决出冠军不是让每支球队和其他31支都打一场，而是两两分组、胜者晋级，最后只需要31场比赛就能知道谁是冠军。选出冠军后，如果想让亚军的产生也高效，只需要重新比较冠军所在那条晋级路径上的球队即可。

放到数组里，先让所有元素两两比较产生一组胜者，胜者再两两比较，依次向上，形成一棵完全二叉树。树的根节点就是全局最小值。取出根节点后，把对应叶子节点置为正无穷，再沿着这条路径重新比较一次，新的根节点就是第二小的值。这个过程保证每次取出一个有序值，只需进行log₂n次比较。

2.2 时间复杂度与堆排序、归并排序的对比

建树阶段需要n-1次比较，之后每次选出一个最小元素需要约log₂n次比较，整体时间复杂度和堆排序一样是O(n log n)。但空间上锦标赛排序需要额外的一棵二叉树，属于非原地算法，这是它不如堆排序普及的主要原因。

不过在工程上，锦标赛思想有一个堆排序替代不了的变体：多路归并。外部排序把大文件拆成多个有序段后，需要把k个有序段合并成一个有序段。每次从k个段的头部选最小值，如果用线性扫描是O(k)，但如果用败者树（胜者树的对称版本），只需要O(log k)。MySQL filesort产生临时文件后的归并阶段，以及各种数据库的external merge sort，底层都是这个套路。

这也是为什么我始终觉得Tournament Sort不是一道孤立的算法题。它表面上是一棵二叉树，实际上是连接选择排序、堆排序、归并排序三者的桥梁。理解了它，你对“排序”这两个字的理解就不再是调用一个sort函数，而是明白在内存放不下时算法如何被迫改变形态。

2.3 MySQL ORDER BY里的树形排序影子

MySQL执行ORDER BY时，会先看排序字段能不能直接走索引。能走索引，B+树本身维护了有序性，直接顺序扫描返回即可。不能走索引，就需要filesort。filesort不是真的“文件排序”，它优先使用内存中的sort buffer（默认sort_buffer_size通常为256KB或更大）。

当sort buffer放不下全部数据时，MySQL会把数据分成多个块，每块内部排序后写成临时文件，最后对这些有序临时文件做多路归并。多路归并的每一步，就是从每个有序块中取当前最小，再比较选出全局最小，这正是锦标赛思想的经典应用。

还有一个容易被忽略的细节：当查询带ORDER BY和LIMIT时，MySQL 8.0会尝试用优先队列（堆）来优化排序，只维护LIMIT大小的堆，而不是把所有行都排好序。这种做法的时间复杂度是O(n log m)，m是LIMIT大小，n是参与排序的行数。如果你只需要前20条，它绝不会傻到把100万行全部排完再截断。理解这一点，对后面深度翻页优化很有帮助。

2.4 一个最小的锦标赛排序演示

我用Python写了一个最直白的演示版本，只为展示算法骨架，生产代码不建议这么写。

def tournament_sort(arr): n = len(arr) size = 1 while size < n: size <<= 1 tree = [float('inf')] * (2 * size) tree[size:size + n] = arr # 自底向上建树，比较得到冠军 for i in range(size - 1, 0, -1): tree[i] = min(tree[2 * i], tree[2 * i + 1]) res = [] for _ in range(n): v = tree[1] res.append(v) # 定位冠军对应的叶子，置为无穷大后重新向上比较 pos = next(i for i in range(size, 2 * size) if tree[i] == v) tree[pos] = float('inf') pos //= 2 while pos: tree[pos] = min(tree[2 * pos], tree[2 * pos + 1]) pos //= 2 return res

注意这个实现用next线性查找冠军叶子，所以实际复杂度不够严谨，只适合演示原理。工程实现需要用一个left/right数组记录每轮比赛赢家来自哪个分支，或者用败者树降低更新代价。演示代码的核心意图是让你看到“每次只更新冠军路径”这件事——这是整个算法最精华的部分。

3. MySQL深度翻页的真实成本：从回表到临时文件

3.1 一条LIMIT 1000000, 20背后的物理操作

先给一个具体的慢查询现场还原。假设我在维护一张订单表orders，已经积累到200万行，业务端做了一个分页列表页，用户翻到第5万页时，前端发起的就是这种请求：

SELECT id, user_id, amount, created_at FROM orders WHERE status = 1 ORDER BY created_at DESC LIMIT 1000000, 20;

这条SQL的意图是跳过前100万行，取接下来的20行。但数据库的执行计划不会聪明到“直接从某个位置开始读”，它必须老老实实扫描到第1000020行，再丢弃前面的1000000行。等于你点了一个20行的外卖，厨师把前面100万份菜全部炒了一遍然后倒掉。

如果ORDER BY的字段没有索引，MySQL还会先把所有满足status=1的行读出来做filesort。更坏的情况是，排序的列不在索引里，需要回表读取完整数据行，再把数据放进sort buffer，排序完成后再次回表取列。光是回表这一步，就可能触发几十万次随机IO。

3.2 用EXPLAIN和实测数据还原慢查询现场

在我本机测试环境里（MySQL 8.0，orders表约200万行，innodb_buffer_pool_size设了1GB），执行上面的SQL，EXPLAIN结果大致是这样的：

EXPLAIN SELECT id, user_id, amount, created_at FROM orders WHERE status = 1 ORDER BY created_at DESC LIMIT 1000000, 20;

rows估算185万，这还只是估算值。实际执行时，由于需要把185万行读进sort buffer并做外部排序，耗时轻松超过900ms。随着offset继续增大，扫描范围还会线性增长。如果把offset换成2000000，这条查询可能直接变成秒级。

EXPLAIN里出现Using filesort，意味着排序过程没有索引可用。即使有二级索引支撑，回表的次数也会被放大到“offset+limit”的规模。这就是为什么很多报表接口翻到后面会越来越慢，不是数据库变卡了，而是每次翻页都在重复做同样的超大排序和超大跳跃。

3.3 翻页越深越慢的三个放大因素

第一个是回表放大。InnoDB的二级索引只存索引列和主键，要取其他字段必须回到聚簇索引。深翻页时回表次数接近offset，这些回表操作对散落的随机主键发起读取，在没有被缓存的情况下每次都可能是物理IO。

第二个是排序放大。如果排序字段没有索引，参与排序的是全部满足条件的行，而不是从第1000000行开始的20行。这意味着一半以上的数据被读进sort buffer又被写出临时文件，做了大量无意义的排序工作。

第三个是重复计算。分页接口每次翻页都是独立SQL，上一页产生的排序结果和扫描位置完全不被重用。用户连续翻10页，数据库就做10次几乎一样的全量排序。页数越深，这个重复成本越离谱。

想解决深翻页，就得从这三个放大因素下手：减少回表、减少排序规模、消灭大offset。

4. 针对深度翻页的SQL改写方案与适用边界

4.1 延迟关联：用覆盖索引先缩小回表范围

延迟关联的核心思路是：先用最小代价查出这一页需要的20个主键，再用主键回表取完整数据。最小代价怎么实现？让子查询的WHERE、排序字段、主键都在同一个覆盖索引里。

对上面的例子，先建一个联合索引(status, created_at, id)或者(created_at, id)，然后改写SQL：

SELECT o.* FROM ( SELECT id, created_at FROM orders WHERE status = 1 ORDER BY created_at DESC LIMIT 1000000, 20 ) AS t JOIN orders o ON o.id = t.id ORDER BY t.created_at DESC;

子查询只扫描覆盖索引，不需要回表取出所有列；索引天然有序，Using filesort会消失；LIMIT阶段处理的都是索引页的小记录，占用sort buffer非常少。拿到20个主键后再JOIN原表，只做20次聚簇索引查询。

我实测这条改写语句耗时降到约55ms，和之前的900ms相比几乎不是一个量级。注意外层又加了一个ORDER BY t.created_at DESC，因为JOIN是乱序匹配的，如果业务要求保持分页顺序，需要在外层重新排序。子查询里同时select id和created_at，是为了外层能够稳定排序。

4.2 游标分页：让offset从SQL里消失

延迟关联依然要扫描offset之前的100万个索引项，虽然比回表全行快，但offset继续增大到百万、千万时还是会感觉到压力。真正让深翻页成本恒定的是游标分页，也叫keyset分页。

思路很简单：客户端记住上一页最后一条记录的排序字段和主键，下一页从这条记录后面接着取。SQL写成这样：

SELECT id, user_id, amount, created_at FROM orders WHERE status = 1 AND (created_at, id) < (:last_created_at, :last_id) ORDER BY created_at DESC, id DESC LIMIT 20;

联合索引(status, created_at, id)可以直接支撑这个查询。数据库通过索引定位到游标位置，然后顺序向后扫描20行，整个过程与offset完全没有关系。不管当前在第几页，查询时间都稳定在个位数毫秒级别。

这个方案最痛的点在于不支持常见的页码跳转。产品要做“跳到第100000页”这种需求，游标分页就无能为力了。所以它更适合信息流、下拉加载、按时间线浏览这类“只关心下一页”的场景。我的建议是：新项目优先按游标分页设计接口，老项目如果需要兼容页码，至少把延迟关联用起来。

4.3 覆盖索引与稳定排序的细节

还有一个常见陷阱：如果排序字段不是唯一列，比如排created_at时同一秒有几十条记录，那么分页结果可能在不同页之间出现重复或遗漏。解决方案也很简单，排序条件里同时带上主键，让排序组合(created_at, id)成为唯一序。前面游标分页的SQL已经通过(id < :last_id)体现了这一约束，延迟关联的SQL也要确保子查询里按created_at, id并列排序。

如果你只需要返回排序字段本身和主键，不想接业务字段，覆盖索引查询就够了：

SELECT id, created_at FROM orders WHERE status = 1 ORDER BY created_at DESC, id DESC LIMIT 1000000, 20;

这种方式几乎没有回表成本，可以当成一个轻量的数据导出查询。但实际业务列表几乎总是要展示多个字段，所以延迟关联仍然是更通用的做法。

4.4 不同深翻页场景的选型对照

我整理了一个决策表，按业务场景直接选即可：

一句话总结：只要有办法绕过offset，就别用offset；如果必须支持跳页，那就把扫描成本从全行回表降为覆盖索引扫描，这是性价比最高的折中。

5. ByteSlice论文精读：字节切片编码的设计与收益

5.1 论文在解决什么问题

如果说前面两章是在“减少数据库做的无用功”，ByteSlice思考的是更底层的事：数据以什么形态放在磁盘上，才能让扫描更快。传统行式存储按行存数据，读一行就要把整行的所有字段读出来，即使你只需要其中两列。列式存储则把同一列的数据连续存放，扫描时只需要读取目标列，天然节省大量IO。

但连续存放只是第一步。分析型查询往往要扫描几亿行数值数据，即使只读一列，数据量依然巨大。ByteSlice就是针对这类定长数值列提出的一种编码：与其把每个整数看成一个整体去压缩，不如把每个整数的字节拆开，按字节位置分组成连续切片，再对每个切片做更有效的压缩。

这套思路之所以有效，是因为数值数据存在天然的字节分布规律。举个例子，int32正数的高位两个字节通常全是0，int64负数的最高位字节又往往是0xFF。把这些高位字节放在一起，你会发现它们的形式非常单一，非常容易被压缩。

5.2 编码过程拆解：从列数据到字节切片

我用一组具体数字演示ByteSlice的处理过程。假设一列int32数据为[1024, 1025, 4096, 4097]，小端序下每个数占4字节：

• 1024 -> 00 04 00 00
• 1025 -> 01 04 00 00
• 4096 -> 00 10 00 00
• 4097 -> 01 10 00 00

ByteSlice不是按行存这4个整数，而是按字节偏移重新组织：

第2、第3字节切片全是0，根本不需要存储；第1字节切片只有两个不同取值，可以用很小的bit宽度做位打包；第0字节切片数值分布相对分散，但也可以配合Delta编码或Varint压缩。

查询时也不需要解码全部切片。比如你要过滤 x > 3000，可以先看高字节切片，如果高字节部分已经说明该值大于或小于阈值，就不用继续处理低位切片。这种按切片级别的Skip逻辑配合SIMD，能够在扫描初期就排除大量不满足条件的行。

5.3 与RLE、字典、Delta编码的横向对比

ByteSlice不是唯一的选择。数据库列存中常见的编码还有几种：

ByteSlice最大优势在于它不依赖数据的排列顺序，不需要相邻值相同或递增，只要数值在字节层面有模式，就能获得压缩收益。这在真实业务里是很常见的：价格、年龄、数量、状态码这些字段往往数值范围不大，但行与行之间未必有规律。

5.4 代价与适用边界

ByteSlice不是没有成本。它要求列是定长数值类型，对VARCHAR/字符串类型基本无能为力；随机写入场景，字节切片后会破坏一行数据的连续性，更新一小块数据可能涉及多个切片的修改，代价很大；实现层面，编码器和解码器都要处理位偏移、切片切分、bit-packing对齐等细节，没有成熟的库支持时开发成本不低。

所以ByteSlice更适合OLAP系统里的只读或追加写表，而不是高并发OLTP。很多列式存储引擎之所以选择它，是因为分析型查询注重扫描吞吐，而OLTP的点查和更新场景完全用不上这种编码。理解这个边界，比记住编码本身更重要。

这类“字节切片”思想给我的启发是：数据的物理布局直接影响查询性能。你在设计MySQL表时，如果能把高频查询的少量字段放在一个宽表里，减少无谓的大字段读入，本质上也是在用更窄的数据布局换取更快的扫描速度。

6. 三个主题连起来看：一条数据库性能优化主线

6.1 算法阶段：排序的优化空间在哪里

回到Tournament Sort。它告诉我们的第一件事是：排序不是一件一锤子买卖的事，信息可以复用。数据库index有序扫描、filesort的优先队列优化、外部归并的败者树，全部建立在这个认知之上。

日常写SQL时，如果你发现ORDER BY在慢查询里出现，先别急着加缓存。问自己三个问题：排序字段能不能命中索引？LIMIT能不能和ORDER BY一起告诉优化器，让它使用堆排序而不是全量排序？排序字段是不是唯一的，能不能加上主键保证稳定？大多数排序慢的问题，问完这三个问题就解决了七成。

6.2 工程阶段：把查询改成可预期的低成本路径

深度翻页优化给我们的工程启发是：查询性能应该可预期，而不是依赖数据量碰运气。用游标分页后，不管第100页还是第10000000页，查询时间都维持在几毫秒；用延迟关联后，回表次数从offset+limit降为limit。这些手段的核心都是把“不确定的全表扫描”改成“确定的索引定位”。

我见过不少团队花大价钱加缓存、上搜索引擎，却忽略了把深翻页SQL改成游标分页这种只需要半天就能完成的改造。优化是有顺序的：先改SQL和索引，再考虑架构层缓存。前者往往是性价比最高的。

6.3 进阶阶段：用存储编码反向影响查询设计

ByteSlice让我意识到，数据库性能优化不仅有“查询层”和“索引层”，还有“存储层”。同样的数据，以行存、列存、字节切片、字典压缩等不同形式存放，查询性能可能差出两个数量级。作为应用开发者，虽然很难直接去改InnoDB的存储格式，但在做表结构设计时可以借鉴这种思想：尽量让行窄一些、让热点列集中一些、避免无意义的宽表和大字段查询。

在线业务如果确实需要大范围报表查询，该考虑把数据同步到分析型引擎时，也可以优先选择支持列存和字节级编码的方案。这不是让你抛弃MySQL，而是知道在什么场景下什么样的存储形态更适合。

6.4 一点个人实操体会

这三个主题我是在一次线上事故里串起来的。当时业务报表接口在深翻页后频繁超时，我第一反应是加索引，加了还是慢，才开始研究EXPLAIN、回表、覆盖索引，最后用延迟关联把耗时降了下来。后来去读列存编码相关的论文，才意识到自己过去对“数据如何存放”的理解一直停留在表结构层面，对物理布局和编码收益几乎没有概念。

这段经历让我形成了一个固定习惯：每遇到一个性能问题，先想清楚它属于算法问题、执行计划问题还是存储表示问题，再决定怎么下手。这个习惯比任何具体SQL技巧都管用。DARTS系列后续也会继续沿着“算法基础、工程优化、论文精读”这个三明治结构来写，下一期打算聊聊Hash Join的底层设计，以及在真实业务里如何选择Join策略。