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同学怎么定了。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180116A0FK5700?refer=cp_1026

扫码关注云+社区