10分钟梳理关系数据库基础知识 四：两阶段多路归并排序

更多腾讯海量技术文章，请关注云加社区：https://cloud.tencent.com/developer

作者：刁寿钧

重要性

今天来复习下两阶段多路归并排序。单独讲一次算法，是因为我觉得这个算法太重要了，不仅仅是对数据库而言。遇到一个不可能完成的大问题，将它划分成许多个小问题，分别求解，再将一系列小问题的解汇聚成大问题的解。这种”由大化小，分而治之“的思路，其实在计算机的许多领域都有闪耀。

问题

假定我们有一张表，10000000行吧，每行记录有100个Byte。这样，整张表粗略地估计为1GB。现在要求我们将这整张表的记录排个序。假设块的大小为4KB，也就是说，一个块中只能填40行记录，整张表占据250000个块。可供数据库排序使用的内存设为50MB，这样能放入内存的只有12800块。

如果所有记录都能放内存里面，那我们在学校里学的什么QuickSort MergeSort HeapSort都能排上用场了，想怎么排怎么排。但我们通过计算已经发现了，绝大多数记录都躺在磁盘上呢，这怎么办？

算法

解决思路就是我们（第一阶段）划分成一个个小部分，让小部分在内存中各自排好序，（第二阶段）再合并成大的结果。

具体来说，我们将250000个块中的12800个块装入内存，排好序，将结果写到磁盘上。这个整个一阶段要花多久呢？对于250000个块，每个块都要一次读一次写，这样就有500000次磁盘IO。假设每个块的读写为15毫秒（取个中间值），那么第一阶段总耗时就是125分钟。第二阶段中，我们将块读出，进行合并。但是我们换个角度，考查每个块的话，我们会发现，每个块都恰好是一次读一次写，同第一阶段一样。所以，整个过程的耗时可估算成250分钟。

块的大小

细心的同学应该已经发现了，在这个算法中，如果我们调大块的大小，那么磁盘IO次数就会减少。那么块是不是越大越好呢？当然不是。块太大的话磁盘上会有更多未利用的空间。当然，InnoDB中page的大小也是可以指定的，默认好像是16KB，具体就看DBA同学怎么定了。