? ? ? ? 少俠我們又見面了护侮。今天我們一起聊聊作為數(shù)據(jù)庫核心算子之一的OrderBy排序算子是如何實(shí)現(xiàn)的拳氢。OrderBy排序算子本質(zhì)是對(duì)二維無序表數(shù)據(jù)按照排序規(guī)則（升序/降序践剂、NULL前排/NULL后排）進(jìn)行排序的一種算法實(shí)現(xiàn)弓摘。而對(duì)二維表排序的本質(zhì)是一維數(shù)據(jù)排序的擴(kuò)展圣蝎。
1 一維排序算法
? ? ? ? 一維數(shù)據(jù)排序常見的算法有冒泡排序刃宵、選擇排序、插入排序徘公、快速排序牲证、希爾排序、歸并排序关面、基數(shù)排序坦袍、計(jì)數(shù)排序、堆排序等太、桶排序十大經(jīng)典排序算法捂齐。不同算法在不同場(chǎng)景優(yōu)劣不同。
????????數(shù)據(jù)庫內(nèi)核非LIMIT場(chǎng)景一般采用快速排序排序缩抡。Postgre內(nèi)核非LIMIT場(chǎng)景底層排序算子采用快速排序加冒泡排序?qū)崿F(xiàn)奠宜，快速排序平均時(shí)間復(fù)雜度O(nlog)，針對(duì)大數(shù)據(jù)量場(chǎng)景應(yīng)用瞻想。而冒泡排序時(shí)間復(fù)雜度O(n^2)压真，針對(duì)小數(shù)據(jù)量場(chǎng)景應(yīng)用（Postgre數(shù)據(jù)量7行以下采用冒泡排序）。LIMIT場(chǎng)景一般采用堆排序?qū)崿F(xiàn)蘑险。堆排序無需將所有數(shù)據(jù)有序輸出滴肿，無需將所有數(shù)據(jù)量全局排序，相對(duì)性能較高漠其。前邊說到一般場(chǎng)景會(huì)采用堆排序?qū)崿F(xiàn)LIMIT場(chǎng)景嘴高，為什么這么說，因?yàn)樵撆判蛩惴ㄟ€要考慮LIMIT的數(shù)量和屎，LIMIT數(shù)據(jù)量較小時(shí)毋庸置疑第一選擇堆排序拴驮，那么隨著LIMIT數(shù)據(jù)量的增長堆排的性能會(huì)隨之降低，可能需要其他算法進(jìn)行優(yōu)化柴信。本文非LIMIT場(chǎng)景采用快速排序奈应，LIMIT場(chǎng)景采用堆排序進(jìn)行講解其實(shí)現(xiàn)原理。
1.1 快速排序
????????快速排序佩憾，又名挖坑填補(bǔ)排序。核心實(shí)現(xiàn)是選取無需序列中間值（理論上的中位數(shù)）萄涯，將無序序列按中間值進(jìn)行分組，小于中間值的全部放到左邊唆鸡，大于或等于中間值的全部放到右邊涝影，將兩組數(shù)據(jù)再按照相同的方式進(jìn)行分組，直到兩個(gè)數(shù)據(jù)分成兩組也就是兩組相對(duì)有序争占，整個(gè)序列達(dá)到有序狀態(tài)（此過程也是相同子問題求解思想）燃逻。
1. 中間值選取
????????中間值選取的好壞直接影響排序的性能，當(dāng)中間值選取相對(duì)極端會(huì)導(dǎo)致時(shí)間快速排序復(fù)雜度退化到O(n^2)臂痕，因此可以對(duì)無需數(shù)據(jù)選取幾個(gè)點(diǎn)進(jìn)行計(jì)算其中位數(shù)作為整個(gè)序列的中間值進(jìn)行排序伯襟。
????????針對(duì)小數(shù)據(jù)量可以三個(gè)點(diǎn)選取方式進(jìn)行計(jì)算平均值，計(jì)算如下：
? ??????????????????????????????????????????????
????????針對(duì)大數(shù)據(jù)量可以采用多個(gè)點(diǎn)選取方式計(jì)算平均值握童，計(jì)算如下：
? ??????????????????????????????????????????????
? ??????????????????????????????????????????????
? ??????????????????????????????????????????????
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
2. 算法原理
1）選取無序序列中中間姆怪，此推演過程"15"為序列中間值，標(biāo)記其中間值數(shù)據(jù)澡绩；兩個(gè)指針標(biāo)記序列首位元素稽揭，后邊移動(dòng)指針對(duì)序列數(shù)據(jù)進(jìn)行排序；pRight指針指向的數(shù)據(jù)與中間值比較肥卡，大于中間值淀衣，向前移動(dòng)；
2）pRight指針指向的數(shù)據(jù)與中間值比較召调，小于中間值膨桥，將pRight指針指向的數(shù)據(jù)覆蓋到pLeft指針指向的數(shù)據(jù)內(nèi)容；pLeft指針向后移動(dòng)唠叛；
3）pLeft指針指向的數(shù)據(jù)與中間值比較只嚣，大于中間值，將pLeft指針指向的數(shù)據(jù)覆蓋到pRight指針指向的數(shù)據(jù)內(nèi)容艺沼；pRight指針向前移動(dòng)册舞；
4）pRight指針指向的數(shù)據(jù)與中間值比較，小于中間值障般，將pRight指針指向的數(shù)據(jù)覆蓋到pLeft指針指向的數(shù)據(jù)內(nèi)容调鲸；pLeft指針向后移動(dòng)；
5）pLeft指針和pRright指針重疊挽荡，將中間值覆蓋到該指針指向的位置藐石，完成一輪分組排序過程。后續(xù)過程以此類推使得最終所有數(shù)據(jù)整體有序定拟。
1.2 堆排序
????????堆排序我們常見的堆有兩種堆于微，一種是大根堆，另一種是小根堆。顧名思義大堆大根堆就是對(duì)頂元素是序列中最大值株依；而小根堆對(duì)頂元素則是序列中的最小值驱证。對(duì)大堆和小堆的選擇依賴數(shù)據(jù)的正序輸出還是反序輸出。
1. 存儲(chǔ)和邏輯結(jié)構(gòu)
????????堆排序的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)本質(zhì)是序列結(jié)構(gòu)恋腕，為了模擬堆（二叉樹結(jié)構(gòu)）使其每輪處理的數(shù)據(jù)時(shí)樹的高度的數(shù)量抹锄，同時(shí)可以輸出前N個(gè)元素有序，后邊的數(shù)據(jù)可以不進(jìn)行處理荠藤，大大降低了時(shí)間復(fù)雜度祈远。因此對(duì)一維序列按照索引的關(guān)系抽象的堆的數(shù)據(jù)結(jié)構(gòu)。當(dāng)前節(jié)點(diǎn)索引為：商源，其左節(jié)點(diǎn)索引為：
，其右節(jié)點(diǎn)索引為：
谋减，當(dāng)前節(jié)點(diǎn)與其左右節(jié)點(diǎn)的索引關(guān)系如下所示：
? ??????????????????????????????????????????????????
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
2. 算法原理
1）建堆過程
????????從堆的最后一個(gè)父節(jié)點(diǎn)向第一個(gè)節(jié)點(diǎn)依次調(diào)整牡彻，調(diào)整思想是選擇當(dāng)前節(jié)點(diǎn)元素、當(dāng)前節(jié)點(diǎn)左節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)中最小的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)交換出爹。也就是說當(dāng)前節(jié)點(diǎn)數(shù)據(jù)要保證比兩個(gè)子節(jié)點(diǎn)數(shù)據(jù)都小庄吼。依次處理到根節(jié)點(diǎn)，當(dāng)前根節(jié)點(diǎn)一定是整個(gè)堆中最小的元素（本例為小根堆）严就。
2）調(diào)整過程
????????將建好的堆堆頂元素與最后一個(gè)元素交換位置总寻；將堆范圍縮小，不包含最后一個(gè)元素梢为，因?yàn)榇藭r(shí)最后一個(gè)元素是有序數(shù)據(jù)渐行，不需要參與堆的調(diào)整和排序過程。
????????上述過程操作后需要進(jìn)一步將堆頂元素進(jìn)行調(diào)整铸董。從當(dāng)前節(jié)點(diǎn)開始依次與左右節(jié)點(diǎn)比較祟印，交換調(diào)整使得當(dāng)前節(jié)點(diǎn)保存的是三個(gè)節(jié)點(diǎn)（當(dāng)前節(jié)點(diǎn)、左節(jié)點(diǎn)粟害、右節(jié)點(diǎn)）中值最小蕴忆，被交換的子節(jié)點(diǎn)再與其子節(jié)點(diǎn)繼續(xù)按此方式調(diào)整，直到堆底為止悲幅。再反復(fù)以上兩個(gè)過程直到滿足輸出LIMIT數(shù)量的數(shù)據(jù)套鹅。
2 二維排序算法
????????數(shù)據(jù)庫OrderBy排序目的是對(duì)二維表數(shù)據(jù)按照排序規(guī)則（升序/降序、NULL前排/NULL后排）進(jìn)行排序汰具。而二維表數(shù)據(jù)排序的基礎(chǔ)是依賴一維數(shù)據(jù)的排序算法進(jìn)一步擴(kuò)展實(shí)現(xiàn)卓鹿。本文將講述三種對(duì)二維表數(shù)據(jù)排序的實(shí)現(xiàn)方式，分別是正向分組排序留荔、正向隊(duì)列排序和反向單列排序减牺，接下來讓我們一一道來。
2.1 反向單列排序
????????反向單列排序與基數(shù)排序的思想類似，對(duì)排序列C1拔疚、C2肥隆、C3反向一次對(duì)每一列排序。先對(duì)C3列進(jìn)行排序稚失，再對(duì)C2列進(jìn)行排序栋艳，最后再對(duì)C1列進(jìn)行排序。對(duì)每一列排序的算法需要選擇穩(wěn)定排序才能保證反向?qū)γ恳涣信判蚝蟮臄?shù)據(jù)整體有序句各。該算法實(shí)現(xiàn)方式相對(duì)簡(jiǎn)單吸占，但性能最低，需要對(duì)每一列數(shù)據(jù)相鄰的數(shù)據(jù)均要比較凿宾。
2.2 正向分組排序
????????數(shù)據(jù)庫多列排序本質(zhì)是在前一列排序后矾屯，對(duì)前一列相等的數(shù)據(jù)范圍內(nèi)再按照下一列排序規(guī)則對(duì)下一列進(jìn)行排序的方式。正向分組排序是將當(dāng)前列相同數(shù)據(jù)范圍內(nèi)的數(shù)據(jù)劃分為一個(gè)分組初厚，然后再對(duì)當(dāng)前分組內(nèi)的數(shù)據(jù)按照下一列排序規(guī)則進(jìn)行下一列排序件蚕，再將下一列排序好的數(shù)據(jù)進(jìn)一步相等數(shù)據(jù)分組，再對(duì)生成的分組按照下一列排序規(guī)則進(jìn)一步排序产禾，依次類推將所有分組所有列的數(shù)據(jù)全部排完也就是整個(gè)數(shù)據(jù)全部有序排作。
1）將C1列按照C1列排序規(guī)則進(jìn)行排序，本次排序規(guī)則所有列均按照升序進(jìn)行排序亚情。
2）根據(jù)第一列排好序的數(shù)據(jù)可以看出前四行數(shù)據(jù)全部相同妄痪，因此可以將前四行數(shù)據(jù)按照第一列的數(shù)據(jù)特性（相等）劃分成一個(gè)分組，再該分組的基礎(chǔ)上對(duì)C2列按照排序規(guī)則（升序）進(jìn)行排序楞件。
3）根據(jù)第二列排序序的數(shù)據(jù)可以看出前三行的數(shù)據(jù)全部相同衫生，因此可以將前三行數(shù)據(jù)按照第二列的數(shù)據(jù)特性（相等）劃分成一個(gè)分組，再該分組的基礎(chǔ)上對(duì)C3列按照排序規(guī)則（升序）進(jìn)行排序土浸。
????????該排序算法相對(duì)第一種排序算法（反向單列排序）性能相對(duì)較高障簿。該算法排序過程是按照列進(jìn)行排序，因此在列存數(shù)據(jù)庫的應(yīng)用場(chǎng)景具有較高性能栅迄，訪問連續(xù)內(nèi)存站故，無序跨大內(nèi)存塊讀取，相性能較高毅舆，優(yōu)勢(shì)較大西篓。
2.3 正向多列排序
? ??????正向多列排序是將要二維表數(shù)據(jù)的每一行看做一個(gè)元素，整體相當(dāng)于對(duì)一維數(shù)據(jù)進(jìn)行排序憋活，每一行的前后順序是否交換需要對(duì)兩行數(shù)據(jù)對(duì)應(yīng)的每一列數(shù)據(jù)進(jìn)行比較岂津。以上圖粉色對(duì)應(yīng)的兩行數(shù)據(jù)為例，所有列數(shù)據(jù)均升序排序悦即，該兩行數(shù)據(jù)C1列均為"200"吮成，對(duì)C2列進(jìn)行比較"100"小于"300"橱乱，因此第一行數(shù)據(jù)相對(duì)小于第二行數(shù)據(jù)，進(jìn)行排序交換處理粱甫。
????????將每行數(shù)據(jù)按照一個(gè)元素泳叠，對(duì)整個(gè)二維表數(shù)據(jù)當(dāng)一維數(shù)據(jù)進(jìn)行排序，使其整個(gè)二維表全部有序茶宵。該排序算子是按照行進(jìn)行排序危纫，因此在行存數(shù)據(jù)庫的應(yīng)用場(chǎng)景具有較高性能，訪問連續(xù)內(nèi)存乌庶，無序跨大內(nèi)存塊讀取种蝶，相性能較高，優(yōu)勢(shì)較大瞒大。
3 總結(jié)
????????總體來說數(shù)據(jù)庫內(nèi)核對(duì)二維表數(shù)據(jù)排序本質(zhì)是對(duì)一維表數(shù)據(jù)排序的擴(kuò)展螃征。對(duì)一維數(shù)據(jù)排序一般采用快速排序和堆排序實(shí)現(xiàn)；對(duì)二維數(shù)據(jù)排序采用正向分組排序透敌、正向多列排序和反向單列排序實(shí)現(xiàn)盯滚。針對(duì)不同的數(shù)據(jù)內(nèi)存模型（行存/列存）、不同的業(yè)務(wù)場(chǎng)景（非LIMIT/LIMIT場(chǎng)景）對(duì)不同算法的選擇拙泽。結(jié)合具體應(yīng)用場(chǎng)景選擇一種最優(yōu)的算法，能大幅度提升排序的計(jì)算性能裸燎。
