排序

1.简介¶

对于无序的集合来说，若想要对数据进行查找和操作，最差的情况是数据库中不存在目标数据，因此复杂度为 $O(n)$ 的，对于范围操作来说性能损耗尤为明显。

保证数据的有序性可以天然的简化问题的规模，这也是数据库在存储表时都会隐式地使用索引的原因，如MySQL默认使用B+树存储数据。

对于数据规模较小，能够全部放入内存的数据集来说，可以使用快排、堆排等效率较高的算法。但对于数据规模较大，不能全部放入内存的数据集来说，采用的主要存储介质是磁盘，对于快排、堆排会产生大量随机I/O的算法来说显然效率不高。

对于磁盘数据库来说，常采用的算法为外部排序。

外部排序的思想是分治，将规模更小的问题逐步合并，从而解决规模更大的问题。

外部排序的流程可以看成是一个二叉树或多叉树，其中叶节点是底层的数据。

节点与其相邻的节点，即其父节点的其他子节点在都完成排序的从而有序情况下进行结果合并，从而得到有序的、更大规模的父节点。

合并的方法为用两个或多个游标指向两个或多个节点的第一个元素，然后比较这些游标指向的元素的大小关系，将极值写入结果中并其游标向后移动。

合理性来源于节点的有序性，则极值只可能出现在节点的头部。

外部排序最基本的形态是二路排序。此时，每一次合并是对两个节点进行合并。

假设需要对 $N$ 个page进行合并，则逻辑二叉树的层数有 $log_2N$ 层。

由于每一层都需要对 $N$ 个 $page$ 进行合并，因此总共需要进行 $N *log_2N$ 个 $page$ 进行操作。

再加上每个 $page$ 会产生两次磁盘I/O，一次是读入，一次是写出，因此总的磁盘I/O复杂度为 $O(2*N*log_2N)$

K路每一次合并是对K个节点进行合并。

假设需要对 $N$ 个page进行合并，则逻辑二叉树的层数有 $log_KN$ 层。

由于每一层都需要对 $N$ 个 $page$ 进行合并，因此总共需要进行 $N*log_KN$ 个 $page$ 进行操作。

再加上每个 $page$ 会产生两次磁盘I/O，一次是读入，一次是写出，因此总的磁盘I/O复杂度为 $O(2*N*log_KN)$

B+树的特性使得可以天然的对数据进行排序。