CMU15-445笔记(八)

Sort

2-Way-External Merge Sort

因为数据库的需要排序的数据可能内存装不下，所以可以分块的来进行排序。

• 首先每次读取B个pages进入内存中
• 然后将他们排序后的副本放入disk中
• 取两个已经排好序的副本进行归并排序，循环，直到所有都排好序
  其实就是一个归并排序
  
  每次从disk中读取页再写回的时候，用到了两次IO，所以每次传递的IO总共是2 * N I/O，需要$log_2(N)$的排序次数，最终加上第一次传递的IO，最终总的IO是
  $$ 2N * (1 + log_2(N))$$
  
  可以从图中看出，每次排序的时候，需要两个buffer page 来存储即将要排序的两个页，然后再有一个page 来存储排序后的结果，所以一共需要三个 buffer page

  Double Buffering Optimization

  就是当一个run 正在排序的时候，将另一个即将要排序的run 预读取到另一个buffer 中

General External Merge Sort

Using B+ Trees For Sorting

Clustered B+Tree

聚簇索引中的B+树的叶子叶子节点已经排好序了，所以直接遍历就行

Unclustered B+Tree

非聚簇索引中，叶子节点存储的是数据的主键/指针，所以需要多进行一次IO才能获取数据

Aggregations

实现有两种方式sort 和 hash

Sort

Hash

有一些是聚合是不需要排序（Group By Distinct）的，普遍情况下Hash速度更快
对于Distin来说，只需要丢弃相同hash值的数据就可以了，Group By只需要将相同hash值的数据聚合在一起。
对于数据过多，内存容量不够的情况来说需要External Hashing Aggregate

External Hashing Aggregate

当内存不足的时候，假设现在有B个buffer page，我们可以使用B-1个buffer page当作分区（少的那一个作为input data的buffer page），对于每个key，我们用h1来进行hash操作，将每个key的数据分别放到B-1个buffer page当中，称作分区，然后分别取出每个分区，对每个分区使用h2来进行hash，将key放入hash table（需要处理最后的碰撞）中，这样就可以得出最后结果。