Greenplum 排序算法

• 语言: 中文（简体）
• 格式: .pdf
• 来源: cn.greenplum.org

摘要

Greenplum中文社区 https://cn.greenplum.org 博文 · 资料 · 文档 · 项目 Greenplum内核揭秘之排序算法 5 ● 内排序算法 ● 外排序算法 ● Greenplum TupleSort ● 排序在Greenplum中的应用 Outline 6 ● 冒泡排序 ● 插入排序 ● 快速排序 ● 堆排序 ● 基数排序 内排序算法 7 快速排序是最常用的排序算法，由Tony Hoare在1959年发明。 快速排序算法的三个步骤： ● 挑选基准值：从数列中挑选出一个基准元素，称为pivot ● 分割：重新排序数组，所有比基准元素小的元素排放到基准元素之前；所有比基 准元素大的元素排放到基准元素之后。分割完成后，我们完成了对基准元素的 排序，即基准元素在数组中的位置不再改变 ● 递归排序子序列：递归地将小于基准元素的子序列和大于基准元素的子序列分 别进行排序 快速排序 8 ● 快速排序算法每次选取一个基准元素，将比基准元素小的排到基准元素左边， 比基准元素大的排到基准元素的右边，从而将待排序数组分成两个子集。 快速排序 6 8 3 2 7 1 7 9 8 7 7 9 6 3 2 1 分治法 9 快速排序 ● 快速排序算法： 10 堆排序是最常用的排序算法，由J.Williams在1964年发明。 ● 堆是一种近似完全二叉树的结构，最大值堆要求每个子节点的键值总是小于父 节点。最小值堆要求每个子节点的键值总是大于父节点。 堆排序算法 ● 步骤1：建立最大值堆,最大元素在堆顶 ● 步骤2：重复将堆顶元组移除并插入到排序数组，更新堆使其保持堆的性质 ● 步骤3：当堆的元素个数为零时，数组排序完毕 堆排序 11 ● 建堆 堆排序 9 5 8 1 3 6 2 1 2 5 9 8 3 6 12 ● 移除堆顶元素 堆排序 2 5 8 1 3 6 9 1 9 5 2 8 3 6 13 ● 重新建堆 堆排序 8 5 6 1 3 2 9 1 9 5 8 6 3 2 14 ● 移除堆顶元素 堆排序 2 5 6 1 3 8 9 1 9 5 2 6 3 8 15 ● 重新建堆 堆排序 6 5 2 1 3 8 9 1 9 5 6 2 3 8 16 ● 移除堆顶元素 堆排序 3 5 2 1 6 8 9 1 9 5 3 2 6 8 17 ● 重新建堆 堆排序 5 3 2 1 6 8 9 1 9 3 5 2 6 8 18 ● 堆只剩一个元素 堆排序 1 2 3 5 6 8 9 5 9 2 1 3 6 8 19 ● 移除堆顶元素，完成排序 堆排序 1 2 3 5 6 8 9 5 9 2 1 3 6 8 20 ● 堆排序算法 堆排序 21 ● 归并排序分为两个阶段，阶段一是分割阶段，将原始待排序数据分成若干个顺 串。阶段二是合并阶段，将所有小顺串合并成一个包含所有数据的大顺串 外排序之归并排序 1 7 4 8 1 7 4 8 1 4 7 8 待排序数据 分割阶段 合并阶段 22 ● 问题一：分割阶段只需要顺序扫描一次外存，最简单的策略是读取外存数据，加 载到内存，当内存用满时，执行快速排序等内排序算法，生成一个顺串。之后清 空内存，继续读取外存数据，如此反复，直到所有外存数据处理完毕。该算法生 成的每一个顺串的大小都不会超过内存的大小，而顺串越小，合并阶段的代价 就越高，需要读取外存的次数也越多，有没有办法在分割阶段就生成大于内存 大小的顺串呢？ 归并排序的三个问题 23 替换选择算法 24 Knuth 5.4.1R替换选择算法： ● 1. 初始化阶段，读取输入元组至内存，并建立最小堆。 ● 2. 弹出堆顶元组，输出到顺串文件的缓冲区，并记录该元组的排序键为 lastkey。 ● 3. 读取新元组，如果元组排序键大于等于lastkey，插入堆顶，并调整堆，使其有 序。 ● 4. 如果新元组排序键小于lastkey，将该元组放入堆尾，并将堆的大小减1。 ● 5. 重复第2步，直至堆大小变为0。 ● 6. 顺串生成完毕。将堆大小重置为N，并重新建堆。重复第2步，开始生成下一 个顺串。 替换选择算法 25 ● 问题二：合并阶段假设存在N个输入缓冲区，如何高效的比较N个输入缓冲区的 最小值，并输出到输出缓冲区？ 归并排序的三个问题 26 ● 假设顺串(长度为L)分布在K个文件中，顺串合并时需要K个输入缓冲区和1个输 出缓冲区，每次选取K个缓冲区的最小值，输出到输出缓冲区。最后，输出缓冲 区输出的顺串长度为L*K ● 算法复杂度 O...