言

如果說各種編程語言是程序員的招式，那么數據結構和算法就相當于程序員的內功。

想寫出精煉、優秀的代碼，不通過不斷的錘煉，是很難做到的。

八大排序算法

排序算法作為數據結構的重要部分，系統地學習一下是很有必要的。

1、排序的概念

排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。

排序分為內部排序和外部排序。

若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。

反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。

2、排序分類

八大排序算法均屬于內部排序。如果按照策略來分類，大致可分為：交換排序、插入排序、選擇排序、歸并排序和基數排序。如下圖所示：

3、算法分析

*直接插入排序

*希爾排序

2.選擇排序

*簡單選擇排序

*堆排序

3.交換排序

*冒泡排序

*快速排序

4.歸并排序

5.基數排序

不穩定排序：簡單選擇排序，快速排序，希爾排序，堆排序

穩定排序：冒泡排序，直接插入排序，歸并排序，奇數排序

1、插入排序

將第一個和第二個元素排好序，然后將第3個元素插入到已經排好序的元素中，依次類推（插入排序最好的情況就是數組已經有序了）

2、希爾排序

因為插入排序每次只能操作一個元素，效率低。元素個數N，取奇數k=N/2，將下標差值為k的數分為一組（一組元素個數看總元素個數決定），在組內構成有序序列，再取k=k/2，將下標差值為k的數分為一組，構成有序序列，直到k=1，然后再進行直接插入排序。

3、簡單選擇排序

選出最小的數和第一個數交換，再在剩余的數中又選擇最小的和第二個數交換，依次類推

4、堆排序

以升序排序為例，利用小根堆的性質（堆頂元素最小）不斷輸出最小元素，直到堆中沒有元素

1.構建小根堆

2.輸出堆頂元素

3.將堆低元素放一個到堆頂，再重新構造成小根堆，再輸出堆頂元素，以此類推

5、冒泡排序

改進1：如果某次冒泡不存在數據交換，則說明已經排序好了，可以直接退出排序

改進2：頭尾進行冒泡，每次把最大的沉底，最小的浮上去，兩邊往中間靠1

6、快速排序

選擇一個基準元素，比基準元素小的放基準元素的前面，比基準元素大的放基準元素的后面，這種動作叫分區，每次分區都把一個數列分成了兩部分，每次分區都使得一個數字有序，然后將基準元素前面部分和后面部分繼續分區，一直分區直到分區的區間中只有一個元素的時候，一個元素的序列肯定是有序的嘛，所以最后一個升序的序列就完成啦。

7、歸并排序

將一個無序的數列一直一分為二，直到分到序列中只有一個數的時候，這個序列肯定是有序的，因為只有一個數，然后將兩個只含有一個數字的序列合并為含有兩個數字的有序序列，這樣一直進行下去，最后就變成了一個大的有序數列

8、基數排序

找到最大的數，開個比最大的數大一點的數組，遍歷每個元素，某個元素為k，則a[k]++,最好遍歷數組a，a[k]等于多少就輸出多少個k。只能處理整型數

具體排序講解

下面針對不同排序進行一一講解。

一、直接插入排序（Insertion Sort)

算法思想：

直接插入排序的核心思想就是：將數組中的所有元素依次跟前面已經排好的元素相比較，如果選擇的元素比已排序的元素小，則交換，直到全部元素都比較過 因此，從上面的描述中我們可以發現，直接插入排序可以用兩個循環完成：

第一層循環：遍歷待比較的所有數組元素

第二層循環：將本輪選擇的元素(selected)與已經排好序的元素(ordered)相比較。如果：selected > ordered，那么將二者交換。

算法代碼：

void print(int a[], int n ,int i){ cout<<i <<":"; for(int j=0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl;} void InsertSort(int a[], int n){ for(int i=1; i<n; i++){ if(a[i] < a[i-1]){ //若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入 int j=i-1;  int x=a[i]; //復制為哨兵，即存儲待排序元素 a[i]=a[i-1]; //先后移一個元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+1]=a[j]; j--; //元素后移 } a[j+1]=x; //插入到正確位置 } print(a,n,i); //打印每趟排序的結果 }
}
int main{ int a[8]={3,1,5,7,2,4,9,6}; InsertSort(a,8); print(a,8,8);}

二、希爾排序（Shell' s Sort）

算法思想:

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

算法步驟：

1.選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2.按增量序列個數k，對序列進行k 趟排序；

3.每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

算法代碼:

void print(int a[], int n ,int i){ cout<<i <<":"; for(int j=0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl;}/** * 直接插入排序的一般形式 * * @param int dk 縮小增量，如果是直接插入排序，dk=1 * */
void ShellInsertSort(int a[], int n, int dk){ for(int i=dk; i<n; ++i){ if(a[i] < a[i-dk]){ //若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入 int j=i-dk;  int x=a[i]; //復制為哨兵，即存儲待排序元素 a[i]=a[i-dk]; //首先后移一個元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+dk]=a[j]; j -=dk; //元素后移 } a[j+dk]=x; //插入到正確位置 } print(a, n,i ); }
}
 // 先按增量d（n/2,n為要排序數的個數進行希爾排序void shellSort(int a[], int n){
 int dk=n/2; while( dk >=1 ){ ShellInsertSort(a, n, dk); dk=dk/2; }}int main{ int a[8]={3,1,5,7,2,4,9,6}; //ShellInsertSort(a,8,1); //直接插入排序 shellSort(a,8); //希爾插入排序 print(a,8,8);}

三、簡單選擇排序（Selection Sort）

算法思想：

簡單選擇排序的實現思想：比較+交換

1. 從待排序序列中，找到關鍵字最小的元素；

2. 如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換；

3. 從余下的 N - 1 個元素中，找出關鍵字最小的元素，重復(1)、(2)步，直到排序結束。因此我們可以發現，簡單選擇排序也是通過兩層循環實現。第一層循環：依次遍歷序列當中的每一個元素 第二層循環：將遍歷得到的當前元素依次與余下的元素進行比較，符合最小元素的條件，則交換。

算法代碼：

void print(int a[], int n ,int i){ cout<<"第"<<i+1 <<"趟 : "; for(int j=0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl;}/** * 數組的最小值 * * @return int 數組的鍵值 */int SelectMinKey(int a[], int n, int i){ int k=i; for(int j=i+1 ;j< n; ++j) { if(a[k] > a[j]) k=j; } return k;}
/** * 選擇排序 * */void selectSort(int a[], int n){ int key, tmp; for(int i=0; i< n; ++i) { key=SelectMinKey(a, n,i); //選擇最小的元素 if(key !=i){ tmp=a[i]; a[i]=a[key]; a[key]=tmp; //最小元素與第i位置元素互換 } print(a, n , i); }}int main{ int a[8]={3,1,5,7,2,4,9,6}; cout<<"初始值："; for(int j=0; j<8; j++){ cout<<a[j] <<" "; } cout<<endl<<endl; selectSort(a, 8); print(a,8,8);}

四、堆排序（Heap Sort）

算法思想：

堆的概念

堆：本質是一種數組對象。特別重要的一點性質：任意的葉子節點小于（或大于）它所有的父節點。對此，又分為大頂堆和小頂堆：

大頂堆要求節點的元素都要大于其孩子。

小頂堆要求節點元素都小于其左右孩子。

兩者對左右孩子的大小關系不做任何要求。

利用堆排序，就是基于大頂堆或者小頂堆的一種排序方法。下面，我們通過大頂堆來實現。

基本思想：堆排序可以按照以下步驟來完成：

1.首先將序列構建稱為大頂堆；（這樣滿足了大頂堆那條性質：位于根節點的元素一定是當前序列的最大值）

2. 取出當前大頂堆的根節點，將其與序列末尾元素進行交換；（此時：序列末尾的元素為已排序的最大值；由于交換了元素，當前位于根節點的堆并不一定滿足大頂堆的性質）

3. 對交換后的n-1個序列元素進行調整，使其滿足大頂堆的性質；

4. 重復2.3步驟，直至堆中只有1個元素為止

下面是基于大頂堆的堆排序算法代碼：

void print(int a[], int n){ for(int j=0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl;}/** * 已知H[s…m]除了H[s] 外均滿足堆的定義 * 調整H[s],使其成為大頂堆.即將對第s個結點為根的子樹篩選,  * * @param H是待調整的堆數組 * @param s是待調整的數組元素的位置 * @param length是數組的長度 */void HeapAdjust(int H[],int s, int length){ int tmp=H[s]; int child=2*s+1; //左孩子結點的位置。(i+1 為當前調整結點的右孩子結點的位置) while (child < length) { if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比當前待調整結點大的孩子結點) ++child ; } if(H[s]<H[child]) { // 如果較大的子結點大于父結點 H[s]=H[child]; // 那么把較大的子結點往上移動，替換它的父結點 s=child; // 重新設置s ,即待調整的下一個結點的位置 child=2*s+1; } else { // 如果當前待調整結點大于它的左右孩子，則不需要調整，直接退出 break; } H[s]=tmp; // 當前待調整的結點放到比其大的孩子結點位置上 } print(H,length);}
/** * 初始堆進行調整 * 將H[0..length-1]建成堆 * 調整完之后第一個元素是序列的最小的元素 */void BuildingHeap(int H[], int length){  //最后一個有孩子的節點的位置 i=(length -1) / 2 for (int i=(length -1) / 2 ; i >=0; --i) HeapAdjust(H,i,length);}/** * 堆排序算法 */void HeapSort(int H[],int length){ //初始堆 BuildingHeap(H, length); //從最后一個元素開始對序列進行調整 for (int i=length - 1; i > 0; --i) { //交換堆頂元素H[0]和堆中最后一個元素 int temp=H[i]; H[i]=H[0]; H[0]=temp; //每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調整 HeapAdjust(H,0,i); }} 
int main{ int H[10]={3,1,5,7,2,4,9,6,10,8}; cout<<"初始值："; print(H,10); HeapSort(H,10); //selectSort(a, 8); cout<<"結果："; print(H,10);
}

五、冒泡排序（Bubble Sort）

算法思想：

冒泡遍歷所有的數據，每次對相鄰元素進行兩兩比較，如果順序和預先規定的順序不一致，則進行位置交換；這樣一次遍歷會將最大或最小的數據上浮到頂端，之后再重復同樣的操作，直到所有的數據有序。這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端。

算法代碼：

void bubbleSort(int a[], int n){ for(int i=0 ; i< n-1; ++i) { for(int j=0; j < n-i-1; ++j) { if(a[j] > a[j+1]) { int tmp=a[j] ; a[j]=a[j+1] ; a[j+1]=tmp; } } }}

六、快速排序（Quick Sort）

算法思想：

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n logn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

算法步驟：

1. 從數列中挑出一個元素，稱為 “基準”（pivot）。

2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。

3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

算法代碼：

void print(int a[], int n){ for(int j=0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl;}
void swap(int *a, int *b){ int tmp=*a; *a=*b; *b=tmp;}
int partition(int a[], int low, int high){ int privotKey=a[low]; //基準元素 while(low < high){ //從表的兩端交替地向中間掃描 while(low < high && a[high] >=privotKey) --high; //從high 所指位置向前搜索，至多到low+1 位置。將比基準元素小的交換到低端 swap(&a[low], &a[high]); while(low < high && a[low] <=privotKey ) ++low; swap(&a[low], &a[high]); } print(a,10); return low;}

void quickSort(int a[], int low, int high){ if(low < high){ int privotLoc=partition(a, low, high); //將表一分為二 quickSort(a, low, privotLoc -1); //遞歸對低子表遞歸排序 quickSort(a, privotLoc + 1, high); //遞歸對高子表遞歸排序 }}
int main{ int a[10]={3,1,5,7,2,4,9,6,10,8}; cout<<"初始值："; print(a,10); quickSort(a,0,9); cout<<"結果："; print(a,10);
}

七、歸并排序（Merge Sort）

算法思想：

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

算法步驟：

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；

2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

4. 重復步驟3直到某一指針達到序列尾；

5. 將另一序列剩下的所有元素直接復制到合并序列尾。

算法代碼：

void print(int a[], int n){ for(int j=0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl;}
//將r[i…m]和r[m +1 …n]歸并到輔助數組rf[i…n]void Merge(ElemType *r,ElemType *rf, int i, int m, int n){ int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k]=r[j++]; else rf[k]=r[i++]; } while(i <=m) rf[k++]=r[i++]; while(j <=n) rf[k++]=r[j++]; print(rf,n+1);}
void MergeSort(ElemType *r, ElemType *rf, int lenght){  int len=1; ElemType *q=r ; ElemType *tmp ; while(len < lenght) { int s=len; len=2 * s ; int i=0; while(i+ len <lenght){ Merge(q, rf, i, i+ s-1, i+ len-1 ); //對等長的兩個子表合并 i=i+ len; } if(i + s < lenght){ Merge(q, rf, i, i+ s -1, lenght -1); //對不等長的兩個子表合并 } tmp=q; q=rf; rf=tmp; //交換q,rf，以保證下一趟歸并時，仍從q 歸并到rf }}

int main{ int a[10]={3,1,5,7,2,4,9,6,10,8}; int b[10]; MergeSort(a, b, 10); print(b,10); cout<<"結果："; print(a,10);}

八、基數排序(Radix Sort)

算法思想：

基數排序：通過序列中各個元素的值，對排序的N個元素進行若干趟的“分配”與“收集”來實現排序。

分配：我們將L[i]中的元素取出，首先確定其個位上的數字，根據該數字分配到與之序號相同的桶中 。

收集：當序列中所有的元素都分配到對應的桶中，再按照順序依次將桶中的元素收集形成新的一個待排序列L 。

對新形成的序列L重復執行分配和收集元素中的十位、百位...直到分配完該序列中的最高位，則排序結束。

算法代碼：

d RadixSort(Node L[],length,maxradix){ int m,n,k,lsp; k=1;m=1; int temp[10][length-1]; Empty(temp); //清空臨時空間 while(k<maxradix) //遍歷所有關鍵字 { for(int i=0;i<length;i++) //分配過程 { if(L[i]<m) Temp[0][n]=L[i]; else Lsp=(L[i]/m)%10; //確定關鍵字 Temp[lsp][n]=L[i]; n++; } CollectElement(L,Temp); //收集 n=0; m=m*10; k++; }}

使用Python實現

一、冒泡排序

冒泡排序算法的運作如下：

● 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

● 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。

● 針對所有的元素重復以上的步驟，除了最后一個。

● 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

以上節選自維基百科

代碼實現：

def bubble_sort(numberlist): length=len(numberlist) for i in range(length): for j in range(1, length - i): if numberlist[j - 1] > numberlist[j]: numberlist[j], numberlist[j - 1]=numberlist[j - 1], numberlist[j] return numberlist

二、選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

以上節選自維基百科

代碼實現：

def findSmallest(arr): # 用于查找出數組中最小的元素，返回最小元素的索引。 smallest=arr[0] smallest_index=0 for i in range(1, len(arr)): if smallest > arr[i]: smallest=arr[i] smallest_index=i return smallest_index
def selectSort(arr): newArr= while arr: smallest=findSmallest(arr) newArr.append(arr.pop(smallest)) return newArr

三、插入排序

步驟如下:

● 從第一個元素開始，該元素可以認為已經被排序

● 取出下一個元素，在已經排序的元素序列中從后向前掃描

● 如果該元素（已排序）大于新元素，將該元素移到下一位置

● 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置

● 將新元素插入到該位置后

重復步驟2~5

以上節選自維基百科

代碼實現:

def insert_sort(data): for k in range(1, len(data)): cur=data[k] j=k while j > 0 and data[j - 1] > cur: data[j]=data[j - 1] j -=1 data[j]=cur return data

四、希爾排序

希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。

以上節選自維基百科

代碼實現：

def shell_sort(numberlist): length=len(numberlist) gap=length // 2 while gap > 0: for i in range(gap, length): temp=numberlist[i] j=i while j >=gap and numberlist[j - gap] > temp: numberlist[j]=numberlist[j - gap] j -=gap numberlist[j]=temp gap=gap // 2 return numberlist

五、歸并排序

原理如下（假設序列共有{displaystyle n}個元素）：

● 將序列每相鄰兩個數字進行歸并操作，形成{displaystyle ceil(n/2)}個序列，排序后每個序列包含兩/一個元素

● 若此時序列數不是1個則將上述序列再次歸并，形成{displaystyle ceil(n/4)}個序列，每個序列包含四/三個元素

● 重復步驟2，直到所有元素排序完畢，即序列數為1

以上節選自維基百科

代碼如下：

def merge(left, right): result= while left and right: if left[0] < right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)) if left: result +=left if right: result +=right return result

def merge_sort(numberlist): if len(numberlist) <=1: return numberlist mid=len(numberlist) // 2 left=numberlist[:mid] right=numberlist[mid:]
 left=merge_sort(left) right=merge_sort(right) return merge(left, right)

六、快速排序從數列中挑出一個元素，稱為“基準”（pivot），

● 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（相同的數可以到任何一邊）。在這個分割結束之后，該基準就處于數列的中間位置。這個稱為分割（partition）操作。

● 遞歸地（recursively）把小于基準值元素的子數列和大于基準值元素的子數列排序。

● 遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

以上節選自維基百科

代碼如下：

def quick_sort(array): if len(array) < 2: return array else: pivot=array[0] less=[i for i in array[1:] if i <=pivot] greater=[i for i in array[1:] if i > pivot] return quick_sort(less) + [pivot] + quick_sort(greater)

七、堆排序

若以升序排序說明，把數組轉換成最大堆積(Max-Heap Heap)，這是一種滿足最大堆積性質(Max-Heap Property)的二叉樹：對于除了根之外的每個節點i, A[parent(i)] ≥ A[i]。

重復從最大堆積取出數值最大的結點(把根結點和最后一個結點交換，把交換后的最后一個結點移出堆)，并讓殘余的堆積維持最大堆積性質。

def heap_sort(numberlist): length=len(numberlist) def sift_down(start, end): root=start while True: child=2 * root + 1 if child > end: break if child + 1 <=end and numberlist[child] < numberlist[child + 1]: child +=1 if numberlist[root] < numberlist[child]: numberlist[root], numberlist[child]=numberlist[child], numberlist[root] root=child else: break
# 創建最大堆 for start in range((length - 2) // 2, -1, -1): sift_down(start, length - 1)
# 堆排序 for end in range(length - 1, 0, -1): numberlist[0], numberlist[end]=numberlist[end], numberlist[0] sift_down(0, end - 1)
 return numberlist

八、計數排序以上節選自維基百科

代碼如下：

def counting_sort(numberlist, maxnumber): # maxnumber為數組中的最大值 length=len(numberlist) # 待排序數組長度 b=[0 for i in range(length)] # 設置輸出序列，初始化為0 c=[0 for i in range(maxnumber+ 1)] # 設置技術序列，初始化為0 for j in numberlist: c[j]=c[j] + 1 for i in range(1, len(c)): c[i]=c[i] + c[i - 1] for j in numberlist: b[c[j] - 1]=j c[j]=c[j] - 1 return b

總結

各種排序的穩定性，時間復雜度和空間復雜度總結：

我們比較時間復雜度函數的情況：

時間復雜度函數O(n)的增長情況

所以對n較大的排序記錄。一般的選擇都是時間復雜度為O(nlog2n)的排序方法。

時間復雜度來說：

(1)平方階(O(n2))排序

各類簡單排序:直接插入、直接選擇和冒泡排序；

(2)線性對數階(O(nlog2n))排序

快速排序、堆排序和歸并排序；

(3)O(n1+§))排序,§是介于0和1之間的常數。

希爾排序

(4)線性階(O(n))排序

基數排序，此外還有桶、箱排序。說明：

當原表有序或基本有序時，直接插入排序和冒泡排序將大大減少比較次數和移動記錄的次數，時間復雜度可降至O（n）；

而快速排序則相反，當原表基本有序時，將蛻化為冒泡排序，時間復雜度提高為O（n2）；

原表是否有序，對簡單選擇排序、堆排序、歸并排序和基數排序的時間復雜度影響不大。

穩定性：

排序算法的穩定性:若待排序的序列中，存在多個具有相同關鍵字的記錄，經過排序， 這些記錄的相對次序保持不變，則稱該算法是穩定的；若經排序后，記錄的相對 次序發生了改變，則稱該算法是不穩定的。

穩定性的好處：排序算法如果是穩定的，那么從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩定，可以避免多余的比較；

穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序

不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序

選擇排序算法準則：

每種排序算法都各有優缺點。因此，在實用時需根據不同情況適當選用，甚至可以將多種方法結合起來使用。

選擇排序算法的依據

影響排序的因素有很多，平均時間復雜度低的算法并不一定就是最優的。相反，有時平均時間復雜度高的算法可能更適合某些特殊情況。同時，選擇算法時還得考慮它的可讀性，以利于軟件的維護。一般而言，需要考慮的因素有以下四點：

1．待排序的記錄數目n的大小；

2．記錄本身數據量的大小，也就是記錄中除關鍵字外的其他信息量的大小；

3．關鍵字的結構及其分布情況；

4．對排序穩定性的要求。

設待排序元素的個數為n.

1）當n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。

快速排序：是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；

堆排序 ： 如果內存空間允許且要求穩定性的，

歸并排序：它有一定數量的數據移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然后再合并，在效率上將有所提高。

2） 當n較大，內存空間允許，且要求穩定性=》歸并排序

3）當n較小，可采用直接插入或直接選擇排序。

直接插入排序：當元素分布有序，直接插入排序將大大減少比較次數和移動記錄的次數。

直接選擇排序 ：元素分布有序，如果不要求穩定性，選擇直接選擇排序

4）一般不使用或不直接使用傳統的冒泡排序。

5）基數排序

它是一種穩定的排序算法，但有一定的局限性：

1、關鍵字可分解。

2、記錄的關鍵字位數較少，如果密集更好

3、如果是數字時，最好是無符號的，否則將增加相應的映射復雜度，可先將其正負分開排序。

總結

以上所述是小編給大家介紹的必須知道的C語言 八大排序算法，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對腳本之家網站的支持！

?2019女性開發者報告：3成16歲就會編程、JS/Python成女性掌握最多語言

?為了讓自己快樂，我在36歲辭職了

文大綱如下

• Sharding-JDBC 的基本用法和基本原理

• 前言

• 1. 我的出生和我的家族

• 2. 我統治的世界和我的職責

• 3. 召喚我的方式

• 4. 我的特性和我的工作方法

• 4.3.1. SQL 解析

• 4.3.2. SQL 路由

• 4.3.3. SQL 改寫

• 4.3.4. SQL 執行

• 4.3.5. 結果歸并

• 4.2.1. 邏輯表和物理表

• 4.2.2. 分片鍵

• 4.2.3. 路由

• 4.2.4. 分片策略和分片算法

• 4.2.5. 綁定表

• 4.2. 一些核心概念

• 4.3. 我處理 SQL 的過程

• 5. 結束語

前言

這是一篇將“介紹 Sharding-JDBC 基本使用方法”作為目標的文章，但筆者卻把大部分文字放在對 Sharding-JDBC 的工作原理的描述上，因為筆者認為原理是每個 IT 打工人學習技術的歸途。

使用框架、中間件、數據庫、工具包等公共組件來組裝出應用系統是我們這一代 IT 打工人工作的常態。對于這些公共組件——比如框架——的學習，有些人的方法是這樣的：避開復雜晦澀的框架原理，僅僅關注它的各種配置、API、注解，在嘗試了這個框架的常用配置項、API、注解的效果之后，就妄稱自己學會了這個框架。這種對技術的膚淺的認知既經不起實踐的考驗，也經不起面試官的考驗，甚至連自己使用這些配置項、API、注解在干什么都沒有明確的認知。

所以，打工人們，還是多學點原理，多看點源碼，讓優秀的設計思想、算法和編程風格沖擊一下自己的大腦吧 :-)

因為 Sharding-JDBC 的設計細節實在太多，因此本文不可能對 Sharding-JDBC 進行面面俱到的講解。筆者在本文中僅僅保留了對 Sharding-JDBC 的核心特性、核心原理的講解，并盡量使用簡單生動的文字進行表達，使讀者閱讀本文后對 Sharding-JDBC 的基本原理和使用有清晰的認知。為了使這些文字盡量擺脫枯燥的味道，文章采用了第一人稱的講述方式，讓 Sharding-JDBC 現身說法，進行自我剖析，希望給大家一個更好的閱讀體驗。

但是，妄圖不動腦子就能對某項技術產生深度認知是絕不可能的，你思考得越多，你得到的越多。這就印證了那句話：“我變禿了，也變強了。”

1. 我的出生和我的家族

我是 Sharding-JDBC，一個關系型數據庫中間件，我的全名是 Apache ShardingSphere JDBC，我被冠以 Apache 這個貴族姓氏是 2020 年 4 月的事情，這意味著我進入了代碼世界的“體制內”。但我還是喜歡別人稱呼我的小名，Sharding-JDBC。

我的創造者在我誕生之后給我講了我的身世：

“

你的誕生是一個必然的結果。

在你誕生之前，傳統軟件的存儲層架構將所有的業務數據存儲到單一數據庫節點，在性能、可用性和運維成本這三方面已經難于滿足互聯網的海量數據場景。

從性能方面來說，由于關系型數據庫大多采用 B+樹類型的索引，在數據量逐漸增大的情況下，索引深度的增加也將使得磁盤訪問的 IO 次數增加，進而導致查詢性能的下降；同時，高并發訪問請求也使得集中式數據庫成為系統的最大瓶頸。

從可用性的方面來講，應用服務器節點能夠隨意水平拓展（水平拓展就是增加應用服務器節點數量）以應對不斷增加的業務流量，這必然導致系統的最終壓力都落在數據庫之上。而單一的數據庫節點，或者簡單的主從架構，已經越來越難以承擔眾多應用服務器節點的數據查詢請求。數據庫的可用性，已成為整個系統的關鍵。

從運維成本方面考慮，隨著數據庫實例中的數據規模的增大，DBA 的運維壓力也會增加，因為數據備份和恢復的時間成本都將隨著數據量的增大而愈發不可控。

這樣看來關系型數據庫似乎難以承擔海量記錄的存儲。

然而，關系型數據庫當今依然占有巨大市場，是各個公司核心業務的基石。在傳統的關系型數據庫無法滿足互聯網場景需要的情況下，將數據存儲到原生支持分布式的 NoSQL 的嘗試越來越多。但 NoSQL 對 SQL 的不兼容性以及生態圈的不完善，使得它們在與關系型數據庫的博弈中處于劣勢，關系型數據庫的地位卻依然不可撼動，未來也難于撼動。

我們目前階段更加關注在原有關系型數據庫的基礎上做增量，使之更好適應海量數據存儲和高并發查詢請求的場景，而不是要顛覆關系型數據庫。

分庫分表方案就是這種增量，它的誕生解決了海量數據存儲和高并發查詢請求的問題。

但是，單一數據庫被分庫分表之后，繁雜的庫和表使得編寫持久層代碼的工程師的思維負擔翻了很多倍，他們需要考慮一個業務 SQL 應該去哪個庫的哪個表里去查詢，查詢到的結果還要進行聚合，如果遇到多表關聯查詢、排序、分頁、事務等等問題，那簡直是一個噩夢。

于是我們創造了你。你可以讓工程師們以像查詢單數據庫實例和單表那樣來查詢被水平分割的庫和表，我們稱之為透明查詢。

你是水平分片世界的神。

”

這使我感到驕傲。

我被定位為一個輕量級 Java 框架，我在 Java 的 JDBC 層提供的額外服務，可以說是一個增強版的 JDBC 驅動，完全兼容 JDBC 和各種 ORM 框架。

• 我適用于任何基于 JDBC 的 ORM 框架，如：JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC。

• 我支持任何第三方的數據庫連接池，如：DBCP, C3P0, BoneCP, Druid, HikariCP 等。

• 我支持任意實現 JDBC 規范的數據庫，目前支持 MySQL，Oracle，SQLServer，PostgreSQL 以及任何遵循 SQL92 標準的數據庫。

我的創造者起初只創造了我一個獨苗，后來為了我的家族的興盛，我的兩個兄弟——Apache ShardingSphere Proxy、Apache ShardingSphere Sidecar 又被創造了出來。前者被定位為透明化的數據庫代理端，提供封裝了數據庫二進制協議的服務端版本，?于完成對異構語?的支持；后者被定位為 Kubernetes 的云原?數據庫代理，以 Sidecar 的形式代理所有對數據庫的訪問。通過無中心、零侵?的?案提供與數據庫交互的的嚙合層，即 Database Mesh，又可稱數據庫?格。

因此，我們這個家族叫做 Apache ShardingSphere，旨在在分布式的場景下更好利用關系型數據庫的計算和存儲能力，而并非實現一個全新的關系型數據庫。我們三個既相互獨立，又能配合使用，均提供標準化的數據分片、分布式事務和數據庫治理功能。

2. 我統治的世界和我的職責

我是 Sharding-JDBC，我生活在一個數據水平分片的世界，我統治著這個世界里被水平拆分后的數據庫和表。

在分片的世界里，數據分片有兩種法則：垂直拆分和水平拆分。

按照業務拆分的方式稱為垂直分片，又稱為縱向拆分，它的核心理念是專庫專用。在拆分之前，一個數據庫由多個數據表構成，每個表對應著不同的業務。而拆分之后，則是按照業務將表進行歸類，分布到不同的數據庫中，從而將壓力分散至不同的數據庫。下圖展示了根據業務需要，將用戶表和訂單表垂直分片到不同的數據庫的方案。

垂直分片往往需要對架構和設計進行調整。通常來講，是來不及應對互聯網業務需求快速變化的；而且，它也并無法真正的解決單點瓶頸。如果垂直拆分之后，表中的數據量依然超過單節點所能承載的閾值，則需要水平分片來進一步處理。

水平分片又稱為橫向拆分。相對于垂直分片，它不再將數據根據業務邏輯分類，而是通過某個字段（或某幾個字段），根據某種規則將數據分散至多個庫或表中，每個分片僅包含數據的一部分。例如：根據主鍵分片，偶數主鍵的記錄放入 0 庫（或表），奇數主鍵的記錄放入 1 庫（或表），如下圖所示。

水平分片從理論上突破了單機數據量處理的瓶頸，并且擴展相對自由，是分庫分表的標準解決方案。我管轄的就是水平分片世界。

通過分庫和分表進行數據的拆分來使得各個表的數據量保持在閾值以下，是應對高并發和海量數據系統的有效手段。此外，使用多主多從的分片方式，可以有效的避免數據單點，從而提升數據架構的可用性。

其實，水平分庫本質上還是在分表，因為被水平拆分后的庫中，都有相同的表分片。

分庫和分表這項工作并不是我來做，我雖然是神，但我還沒有神到能理解你們這些工程師的業務設計和架構設計，從而自動把你們的業務數據庫和業務表進行分片。對哪部分進行分片、怎樣分片、分多少份，這些工作全部由這些工程師進行。當這些分庫分表的工作被完成后，你們只需要在我的配置文件中或者通過我的 API 告訴我這些拆分規則（這就是后文要提到的分片策略）即可，剩下的事情，交給我去做。

我是 Sharding-JDBC，我的職責是盡量透明化水平分庫分表所帶來的影響，讓使用方盡量像使用一個數據庫一樣使用水平分片之后的數據庫集群，或者像使用一個數據表一樣使用水平分片之后的數據表。由于我的治理，每個服務器節點只能看到一個邏輯上的數據庫節點，和其中的多個邏輯表，它們看不到真正存在于物理世界中的被水平分割的多個數據庫分片和被水平分割的多個數據表分片。服務器節點看到的簡單的持久層結構，其實是我苦心營造的幻象。

而為了營造這種幻象，我在幕后付出了很多。

當一個 Java 應用服務器節點將一個查詢 SQL 交給我之后，我要做下面幾件事：

1）SQL 解析：解析分為詞法解析和語法解析。我先通過詞法解析器將這句 SQL 拆分為一個個不可再分的單詞，再使用語法解析器對 SQL 進行理解，并最終提煉出解析上下文。簡單來說就是我要理解這句 SQL，明白它的構造和行為，這是下面的優化、路由、改寫、執行和歸并的基礎。

2）SQL 路由：我根據解析上下文匹配用戶對這句 SQL 所涉及的庫和表配置的分片策略（關于用戶配置的分片策略，我后文會慢慢解釋），并根據分片策略生成路由后的 SQL。路由后的 SQL 有一條或多條，每一條都對應著各自的真實物理分片。

3）SQL 改寫：我將 SQL 改寫為在真實數據庫中可以正確執行的語句（邏輯 SQL 到物理 SQL 的映射，例如把邏輯表名改成帶編號的分片表名）。

4）SQL 執行：我通過多線程執行器異步執行路由和改寫之后得到的 SQL 語句。

5）結果歸并：我將多個執行結果集歸并以便于通過統一的 JDBC 接口輸出。

如果你連讀這段工作流程都很困難，那你就能明白我在這個水平分片的世界里有多辛苦。關于這段工作流程，我會在后文慢慢說給你聽。

3. 召喚我的方式

我是 Sharding-JDBC，我被定位為一個輕量級數據庫中間件，當你們召喚我去統治水平拆分后的數據庫和數據表時，只需要做下面幾件事：

1）引入依賴包。

maven 是統治依賴包世界的神，在他誕生之后，一切對 jar 包的引用就變得簡單了。向 maven 獲取我的 jar 包，咒語是：

<dependency>
<groupId>org.apache.shardingsphere</groupId>
<artifactId>shardingsphere-jdbc-core</artifactId>
<version>${latest.release.version}</version>
</dependency>

于是，我就出現在了這個項目中！

如果你們構建的項目已經被 Springboot 統治了（Springboot 是 Spring 的繼任者，Spring 是統治對象世界的神，Springboot 繼承了 Spring 的統治法則，并簡化了 Spring 的配置），那么就可以向 maven 獲取我的 springboot starter jar 包，咒語是：

<dependency>
<groupId>org.apache.shardingsphere</groupId>
<artifactId>shardingsphere-jdbc-spring-boot-starter</artifactId>
<version>${shardingsphere.version}</version>
</dependency>

這樣，我就能和 Springboot 神共存于同一個項目。

2）進行水平分片規則配置。

你們要把水平分片規則配置告訴我，這樣我才能知道你們是怎樣水平拆分數據庫和數據表的。你們可以通過我提供的 Java API，或者配置文件告訴我分片規則。

如果是以 Java API 的方式進行配置，示例如下：

// 配置真實數據源
Map<String, DataSource> dataSourceMap=new HashMap<>;
// 配置第 1 個數據源
BasicDataSource dataSource1=new BasicDataSource;
dataSource1.setDriverClassName("com.mysql.jdbc.Driver");
dataSource1.setUrl("jdbc:mysql://localhost:3306/ds0");
dataSource1.setUsername("root");
dataSource1.setPassword("");
dataSourceMap.put("ds0", dataSource1);
// 配置第 2 個數據源
BasicDataSource dataSource2=new BasicDataSource;
dataSource2.setDriverClassName("com.mysql.jdbc.Driver");
dataSource2.setUrl("jdbc:mysql://localhost:3306/ds1");
dataSource2.setUsername("root");
dataSource2.setPassword("");
dataSourceMap.put("ds1", dataSource2);
// 配置 t_order 表規則
ShardingTableRuleConfiguration orderTableRuleConfig 
=new ShardingTableRuleConfiguration(
"t_order", 
"ds${0..1}.t_order${0..1}"
);
// 配置 t_order 被拆分到多個子庫的策略
orderTableRuleConfig.setDatabaseShardingStrategy(
new StandardShardingStrategyConfiguration(
"user_id", 
"dbShardingAlgorithm"
)
);
// 配置 t_order 被拆分到多個子表的策略
orderTableRuleConfig.setTableShardingStrategy(
new StandardShardingStrategyConfiguration(
"order_id", 
"tableShardingAlgorithm"
)
);
// 省略配置 t_order_item 表規則...
// ...
// 配置分片規則
ShardingRuleConfiguration shardingRuleConfig=new ShardingRuleConfiguration;
shardingRuleConfig.getTables.add(orderTableRuleConfig);
// 配置 t_order 被拆分到多個子庫的算法
Properties dbShardingAlgorithmrProps=new Properties;
dbShardingAlgorithmrProps.setProperty(
"algorithm-expression", 
"ds${user_id % 2}"
);
shardingRuleConfig.getShardingAlgorithms.put(
"dbShardingAlgorithm", 
new ShardingSphereAlgorithmConfiguration("INLINE", dbShardingAlgorithmrProps)
);
// 配置 t_order 被拆分到多個子表的算法
Properties tableShardingAlgorithmrProps=new Properties;
tableShardingAlgorithmrProps.setProperty(
"algorithm-expression", 
"t_order${order_id % 2}"
);
shardingRuleConfig.getShardingAlgorithms.put(
"tableShardingAlgorithm", 
new ShardingSphereAlgorithmConfiguration("INLINE", tableShardingAlgorithmrProps)
);

這段配置代碼中涉及的 t_order 表（存儲訂單的基本信息）的表結構為：

這段配置代碼描述了對 t_order 表進行的如下圖所示的數據表水平分片（對 t_order_item 表也要進行類似的水平分片，但是這部分配置省略了）：

在這段配置中，或許你們注意到了一些奇怪的表達式：

ds$->{0..1}.t_order$->{0..1}
ds_${user_id % 2}
t_order_${order_id % 2}

這些表達式被稱為 Groovy 表達式，它們的含義很容易識別：

1）對 t_order 進行兩種維度的拆分：數據庫維度和表維度數；

2）在數據庫維度，t_order.user_id % 2==0 的記錄全部落到 ds0，t_order.user_id % 2==1 的記錄全部落到 ds1；（有人稱這一過程為水平分庫，其實它的本質還是在水平地分表，只不過依據表中 user_id 的不同把拆分的后的表放入兩個數據庫實例。）

3）在表維度，t_order.order_id% 2==0 的記錄全部落到 t_order0，t_order.order_id% 2==1 的記錄全部落到 t_order1。

4）對記錄的讀和寫都按照這種方向進行，“方向”，就是分片方式，就是路由。

我允許你們這些工程師使用這種簡潔的 Groovy 表達式告訴我你們設置的分片策略和分片算法。但是這種方式所能表達的含義是有限的。因此，我提供了分片策略接口和分片算法接口讓你們利用 Java 代碼盡情表達更為復雜的分片策略和分片算法。關于這一點，我將在《我的特性和工作方法》這一章詳述。

而且在這里我要先告訴你，分片算法是分片策略的組成部分，分片策略設置=分片鍵設置+分片算法設置。上述配置里使用的策略是 Inline 類型的分片策略，使用的算法是 Inline 類型的行表達式算法，你或許不清楚我現在講的這些術語，不要著急，我會在《我的特性和工作方法》這一章詳述。

如果是以配置文件的方式進行配置，示例如下（這里以我的 springboot starter 包的 properties 配置文件為例）：

# 配置真實數據源
spring.shardingsphere.datasource.names=ds0,ds1
# 配置第 1 個數據源
spring.shardingsphere.datasource.ds0.type=org.apache.commons.dbcp2.BasicDataSource
spring.shardingsphere.datasource.ds0.driver-class-name=com.mysql.jdbc.Driver
spring.shardingsphere.datasource.ds0.url=jdbc:mysql://localhost:3306/ds0
spring.shardingsphere.datasource.ds0.username=root
spring.shardingsphere.datasource.ds0.password=
# 配置第 2 個數據源
spring.shardingsphere.datasource.ds1.type=org.apache.commons.dbcp2.BasicDataSource
spring.shardingsphere.datasource.ds1.driver-class-name=com.mysql.jdbc.Driver
spring.shardingsphere.datasource.ds1.url=jdbc:mysql://localhost:3306/ds1
spring.shardingsphere.datasource.ds1.username=root
spring.shardingsphere.datasource.ds1.password=
# 配置 t_order 表規則
spring.shardingsphere.rules.sharding.tables.t_order.actual-data-nodes=ds$->{0..1}.t_order$->{0..1}
# 配置 t_order 被拆分到多個子庫的策略
spring.shardingsphere.rules.sharding.tables.t_order.database-strategy.standard.sharding-column=user_id
spring.shardingsphere.rules.sharding.tables.t_order.database-strategy.standard.sharding-algorithm-name=database_inline
# 配置 t_order 被拆分到多個子表的策略
spring.shardingsphere.rules.sharding.tables.t_order.table-strategy.standard.sharding-column=order_id
spring.shardingsphere.rules.sharding.tables.t_order.table-strategy.standard.sharding-algorithm-name=table_inline
# 省略配置 t_order_item 表規則...
# ...
# 配置 t_order 被拆分到多個子庫的算法
spring.shardingsphere.rules.sharding.sharding-algorithms.database_inline.type=INLINE
spring.shardingsphere.rules.sharding.sharding-algorithms.database_inline.props.algorithm-expression=ds_${user_id % 2}
# 配置 t_order 被拆分到多個子表的算法
spring.shardingsphere.rules.sharding.sharding-algorithms.table_inline.type=INLINE
spring.shardingsphere.rules.sharding.sharding-algorithms.table_inline.props.algorithm-expression=t_order_${order_id % 2}

這段配置文件的語義和上面的 Java 配置代碼同義。

3）創建數據源。

若使用上文所示的 Java API 進行配置，則可以通過 ShardingSphereDataSourceFactory 工廠創建數據源，該工廠產生一個 ShardingSphereDataSource 實例，ShardingSphereDataSource 實現自 JDBC 的標準接口 DataSource（所以 ShardingSphereDataSource 實例也是接口 DataSource 的實例）。之后，就可以通過 dataSource 調用原生 JDBC 接口來執行 SQL 查詢，或者將 dataSource 配置到 JPA，MyBatis 等 ORM 框架來執行 SQL 查詢。

// 創建 ShardingSphereDataSource
DataSource dataSource=ShardingSphereDataSourceFactory.createDataSource(
dataSourceMap, 
Collections.singleton(shardingRuleConfig, new Properties)
);

若使用上文所示的基于 springboot starter 的 properties 配置文件進行分片配置，則可以直接通過 Spring 提供的自動注入的方式獲得數據源實例 dataSource（同樣，這也是一個 ShardingSphereDataSource 實例）。之后，就可以通過 dataSource 調用原生 JDBC 接口來執行 SQL 查詢，或者將 dataSource 配置到 JPA，MyBatis 等 ORM 框架來執行 SQL 查詢。

/**
* 注入一個 ShardingSphereDataSource 實例
*/
@Resource
private DataSource dataSource;

有了 dataSource（以上兩種方式產生的 dataSource 沒有區別，都是 ShardingSphereDataSource 的一個實例，業務代碼將 SQL 交給這個 dataSource，也就是交到了我的手中），就可以執行 SQL 查詢了。

4）執行 SQL。這里給出 dataSource 調用原生 JDBC 接口來執行 SQL 查詢的示例：

String sql="SELECT i.* FROM t_order o JOIN t_order_item i ON o.order_id=i.order_id WHERE o.user_id=? AND o.order_id=?";
try (
Connection conn=dataSource.getConnection;
PreparedStatement ps=conn.prepareStatement(sql)
) {
ps.setInt(1, 10);
ps.setInt(2, 1000);
try (
ResultSet rs=preparedStatement.executeQuery
) {
while(rs.next) {
// ...
}
}
}

在這個示例中，Java 代碼調用 dataSource 的 JDBC 接口時，只感覺自己在對一個邏輯庫中的兩個邏輯表進行關聯查詢，并沒有意識到物理分片的存在。而背后是我在進行 SQL 語句的解析、路由、改寫、執行和結果歸并！

4. 我的特性和我的工作方法

4.2. 一些核心概念

我是 Sharding-JDBC，我是統治水平分片世界的神，我要向你們解釋我的特性和治理方法。在此之前，我要給出一系列用于描述我的術語。

4.2.1. 邏輯表和物理表

例如，訂單表根據主鍵尾數被水平拆分為 10 張表，分別是 t_order0 到 t_order9，它們的邏輯表名為 t_order，而 t_order0 到 t_order9 就是物理表。

4.2.2. 分片鍵

例如，若根據訂單表中的訂單主鍵的尾數取模結果進行水平分片，則訂單主鍵為分片鍵。訂單表既可以根據單個分片鍵進行分片，也同樣可以根據多個分片鍵（例如 order_id 和 user_id）進行分片。

4.2.3. 路由

應用程序服務器將針對邏輯表編寫的 SQL 交給我，我在執行前，要找到 SQL 語句里包含的查詢條件（where ......）所對應的分片（物理表），然后再針對這些分片進行查詢，這個找分片的過程叫做路由。

而怎樣找分片，是由你們在分片策略中告訴我的。

4.2.4. 分片策略和分片算法

在上文的配置示例中，有如下的一段：

......
// 配置 t_order 被拆分到多個子庫的策略
orderTableRuleConfig.setDatabaseShardingStrategy(
new StandardShardingStrategyConfiguration(
"user_id", 
"dbShardingAlgorithm"
)
);
// 配置 t_order 被拆分到多個子表的策略
orderTableRuleConfig.setTableShardingStrategy(
new StandardShardingStrategyConfiguration(
"order_id", 
"tableShardingAlgorithm"
)
);
......
ShardingRuleConfiguration shardingRuleConfig=new ShardingRuleConfiguration;
shardingRuleConfig.getTables.add(orderTableRuleConfig);
// 配置 t_order 被拆分到多個子庫的算法
Properties dbShardingAlgorithmrProps=new Properties;
dbShardingAlgorithmrProps.setProperty(
"algorithm-expression", 
"ds${user_id % 2}"
);
shardingRuleConfig.getShardingAlgorithms.put(
"dbShardingAlgorithm", 
new ShardingSphereAlgorithmConfiguration("INLINE", dbShardingAlgorithmrProps)
);
// 配置 t_order 被拆分到多個子表的算法
Properties tableShardingAlgorithmrProps=new Properties;
tableShardingAlgorithmrProps.setProperty(
"algorithm-expression", 
"t_order${order_id % 2}"
);
shardingRuleConfig.getShardingAlgorithms.put(
"tableShardingAlgorithm", 
new ShardingSphereAlgorithmConfiguration("INLINE", tableShardingAlgorithmrProps)
);
......

它們表達的就是對 t_order 表進行的分片策略和分片算法的配置。

上文說到，我允許你們這些工程師使用簡潔的 Groovy 表達式告訴我你們設置的分片策略和分片算法。但是這種方式所能表達的含義是有限的。因此，我提供了分片策略接口和分片算法接口讓你們利用靈活的 Java 代碼盡情表達更為復雜的分片策略和分片算法。

所謂分片策略，就是分片鍵和分片算法的組合，由于分片算法的獨立性，我將其獨立抽離出來，由你們自己實現，也就是告訴我數據是怎么根據分片鍵的值找到對應的分片，進而對這些分片執行 SQL 查詢。

當然我也提供了一些內置的簡單算法的實現。上面提到的基于 Groovy 表達式的分片算法就是我內置的一種算法實現，你們只要給我一段語義準確無誤的 Groovy 表達式，我就能知道怎么根據分片鍵的值找到對應的分片。

我的分片策略有兩個維度，如下圖所示，分別是數據源分片策略（databaseShardingStrategy）和表分片策略（tableShardingStrategy）。數據源分片策略表示數據被路由到目標物理數據庫的策略，表分片策略表示數據被路由到目標物理表的策略。表分片策略是依賴于數據源分片策略的，也就是說要先分庫再分表，當然也可以只分表。

我目前可以提供如下幾種分片（無論是對庫分片還是對表分片）策略：標準分片策略（使用精確分片算法或者范圍分片算法）、復合分片策略（使用符合分片算法）、Hint 分片策略（使用 Hint 分片算法）、Inline 分片策略（使用 Grovvy 表達式作為分片算法）、不分片策略（不使用分片算法）。

我的 Jar 包源碼里的策略類和算法接口如下：

一、標準分片策略

標準分片策略 StandardShardingStrategy 的源代碼（部分）如下，這是一個 final class。

package org.apache.shardingsphere.core.strategy.route.standard;
......
public final classStandardShardingStrategyimplementsShardingStrategy{
private final String shardingColumn;
/**
* 要配合 PreciseShardingAlgorithm 或 RangeShardingAlgorithm 使用
* 標準分片策略
*/
private final PreciseShardingAlgorithm preciseShardingAlgorithm;
private final RangeShardingAlgorithm rangeShardingAlgorithm;
publicStandardShardingStrategy(
// 傳入分片配置
final StandardShardingStrategyConfiguration standardShardingStrategyConfig
) {
......
// 從配置中提取分片鍵
shardingColumn=standardShardingStrategyConfig.getShardingColumn;
// 從配置中提取分片算法
preciseShardingAlgorithm=standardShardingStrategyConfig.getPreciseShardingAlgorithm;
rangeShardingAlgorithm=standardShardingStrategyConfig.getRangeShardingAlgorithm;
}
@Override
public Collection<String> doSharding(
// 所有可能的分片表(或分片庫)名稱
final Collection<String> availableTargetNames, 
// 分片鍵的值
final Collection<RouteValue> shardingValues, 
final ConfigurationProperties properties
) {
RouteValue shardingValue=shardingValues.iterator.next;
Collection<String> shardingResult 
=shardingValue instanceof ListRouteValue
// 處理精確分片
? doSharding(availableTargetNames, (ListRouteValue) shardingValue) 
// 處理范圍分片
: doSharding(availableTargetNames, (RangeRouteValue) shardingValue);
Collection<String> result=new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
result.addAll(shardingResult);
// 根據分片鍵的值，找到對應的分片表(或分片庫)名稱并返回
return result;
}
/**
* 處理范圍分片
*/
@SuppressWarnings("unchecked")
private Collection<String> doSharding(
// 所有可能的分片表(或分片庫)名稱
final Collection<String> availableTargetNames, 
// 分片鍵的值
final RangeRouteValue<?> shardingValue
) {
......
// 調用 rangeShardingAlgorithm.doSharding根據分片鍵的值找到對應的
// 分片表(或分片庫)名稱并返回，rangeShardingAlgorithm.doSharding
// 由你們自己實現
return rangeShardingAlgorithm.doSharding(
availableTargetNames, 
new RangeShardingValue(
shardingValue.getTableName, 
shardingValue.getColumnName, 
shardingValue.getValueRange
)
);
}
/**
* 處理精確分片
*/
@SuppressWarnings("unchecked")
private Collection<String> doSharding(
// 所有可能的分片表(或分片庫)名稱
final Collection<String> availableTargetNames, 
// 分片鍵的值
final ListRouteValue<?> shardingValue
) {
Collection<String> result=new LinkedList<>;
for (Comparable<?> each : shardingValue.getValues) {
// 調用 preciseShardingAlgorithm.doSharding根據分片鍵的值找到對應的
// 分片表(或分片庫)名稱并返回，preciseShardingAlgorithm.doSharding
// 由你們自己實現
String target 
=preciseShardingAlgorithm.doSharding(
availableTargetNames, 
new PreciseShardingValue(
shardingValue.getTableName, 
shardingValue.getColumnName, 
each
)
);
if ( !=target) {
result.add(target);
}
}
return result;
}
/**
* 獲取所有的分片鍵
*/
@Override
public Collection<String> getShardingColumns {
Collection<String> result=new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
result.add(shardingColumn);
return result;
}
}

其中 PreciseShardingAlgorithm（接口）和 RangeShardingAlgorithm（接口）的源代碼分別為：

package org.apache.shardingsphere.api.sharding.standard;
......
public interface PreciseShardingAlgorithm<T extends Comparable<?>> 
extends ShardingAlgorithm {
/**
* @param 所有可能的分片表(或分片庫)名稱
* @param 分片鍵的值
* @return 根據分片鍵的值，找到對應的分片表(或分片庫)名稱并返回
*/
String doSharding(
Collection<String> availableTargetNames, 
PreciseShardingValue<T> shardingValue
);
}

package org.apache.shardingsphere.api.sharding.standard;
......
public interface RangeShardingAlgorithm<T extends Comparable<?>> 
extends ShardingAlgorithm {
/**
* @param 所有可能的分片表(或分片庫)名稱
* @param 分片鍵的值
* @return 根據分片鍵的值，找到對應的分片表(或分片庫)名稱并返回
*/
Collection<String> doSharding(
Collection<String> availableTargetNames, 
RangeShardingValue<T> shardingValue
);
}

標準分片策略提供對 SQL 語句中的操作符=、>、 <、>=、<=、IN 和 BETWEEN AND 的分片操支持。

標準分片策略只支持單分片鍵，例如對 t_order 表只根據 order_id 分片。標準分片策略提供 PreciseShardingAlgorithm（接口）和 RangeShardingAlgorithm（接口）兩個分片算法。PreciseShardingAlgorithm（接口）顧名思義用于處理操作符=和 IN 的精確分片。RangeShardingAlgorithm （接口）顧名思義用于處理操作符 BETWEEN AND、>、<、>=、<=的范圍分片。

我舉個例子幫助你理解以上兩段話的含義。以 t_order 為例，假如你使用 order_id 作為 t_order 的分片鍵，并設計了以下的分片策略：

策略一：設置 6 個分片
t_order.order_id % 6==0 的查詢分片到 t_order0
t_order.order_id % 6==1 的查詢分片到 t_order1
t_order.order_id % 6==2 的查詢分片到 t_order2
t_order.order_id % 6==3 的查詢分片到 t_order3
t_order.order_id % 6==4 的查詢分片到 t_order4
t_order.order_id % 6==5 的查詢分片到 t_order5
策略二：設置 2 個分片
t_order.order_id % 6 in (0,2,4) 的查詢分片到 t_order1
t_order.order_id % 6 in (1,3,5) 的查詢分片到 t_order1
策略三：經過估算訂單不超過 60000 個，設置 6 個分片
t_order.order_id between 0 and 10000 的查詢分片到 t_order0
t_order.order_id between 10000 and 20000 的查詢分片到 t_order1
t_order.order_id between 20000 and 30000 的查詢分片到 t_order2
t_order.order_id between 30000 and 40000 的查詢分片到 t_order3
t_order.order_id between 40000 and 50000 的查詢分片到 t_order4
t_order.order_id between 50000 and 60000 的查詢分片到 t_order5
策略四：經過估算訂單不超過 20000 個，設置 2 個分片
t_order.order_id <=10000 的查詢分片到 t_order0
t_order.order_id >10000 的查詢分片到 t_order1
......

那你就可以把以下三項：

1）分片鍵 order_id

2）描述以上分片策略內容的 PreciseShardingAlgorithm（接口）的實現類或 RangeShardingAlgorithm（接口）的實現類

3）前兩項（即分片策略）的作用目標 t_order 表

寫到分片配置里（無論是通過配置 API 還是通過配置文件），那我就能知道如何去路由 SQL，即根據分片鍵的值，找到對應的分片表(或分片庫)。

有了這些配置，我就能幫你們透明處理如下 SQL 語句，不管實際的物理分片是怎樣的：

-- 注：使用 t_order.order_id 作為 t_order 表的分片鍵
SELECT o.* FROM t_order o WHERE o.order_id=10;
SELECT o.* FROM t_order o WHERE o.order_id IN (10, 11);
SELECT o.* FROM t_order o WHERE o.order_id > 10;
SELECT o.* FROM t_order o WHERE o.order_id <=11;
SELECT o.* FROM t_order o WHERE o.order_id BETWEEN 10 AND 12;
......
INSERT INTO t_order(order_id, user_id) VALUES (20, 1001);
......
DELETE FROM t_order o WHERE o.order_id=10;
DELETE FROM t_order o WHERE o.order_id IN (10, 11);
DELETE FROM t_order o WHERE o.order_id > 10;
DELETE FROM t_order o WHERE o.order_id <=11;
DELETE FROM t_order o WHERE o.order_id BETWEEN 10 AND 12;
......
UPDATE t_order o SET o.update_time=NOW WHERE o.order_id=10;
......

二、復合分片策略

復合分片策略 ComplexShardingStrategy 的源代碼（部分）如下，這是一個 final class。

package org.apache.shardingsphere.core.strategy.route.complex;
......
public final classComplexShardingStrategyimplementsShardingStrategy{
@Getter
private final Collection<String> shardingColumns;
/**
* 要配合 ComplexKeysShardingAlgorithm 使用復合分片策略
*/
private final ComplexKeysShardingAlgorithm shardingAlgorithm;
publicComplexShardingStrategy(
// 傳入分片配置
final ComplexShardingStrategyConfiguration complexShardingStrategyConfig
) {
......
// 從配置中提取分片鍵
shardingColumns=new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
shardingColumns.addAll(
Splitter
.on(",")
.trimResults
.splitToList(complexShardingStrategyConfig.getShardingColumns)
);
// 從配置中提取分片算法
shardingAlgorithm=complexShardingStrategyConfig.getShardingAlgorithm;
}
@SuppressWarnings("unchecked")
@Override
public Collection<String> doSharding(
// 所有可能的分片表(或分片庫)名稱
final Collection<String> availableTargetNames, 
// 分片鍵的值
final Collection<RouteValue> shardingValues, 
final ConfigurationProperties properties
) {
Map<String, Collection<Comparable<?>>> columnShardingValues 
=new HashMap<>(shardingValues.size, 1);
Map<String, Range<Comparable<?>>> columnRangeValues 
=new HashMap<>(shardingValues.size, 1);
String logicTableName="";
// 提取多個分片鍵的值
for (RouteValue each : shardingValues) {
if (each instanceof ListRouteValue) {
columnShardingValues.put(
each.getColumnName, 
((ListRouteValue) each).getValues
);
} else if (each instanceof RangeRouteValue) {
columnRangeValues.put(
each.getColumnName, 
((RangeRouteValue) each).getValueRange
);
}
logicTableName=each.getTableName;
}
Collection<String> shardingResult 
// 調用 shardingAlgorithm.doSharding根據分片鍵的值找到對應的
// 分片表(或分片庫)名稱并返回，shardingAlgorithm.doSharding
// 由你們自己實現
=shardingAlgorithm.doSharding(
availableTargetNames, 
new ComplexKeysShardingValue(
logicTableName, 
columnShardingValues, 
columnRangeValues)
);
Collection<String> result=new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
result.addAll(shardingResult);
// 根據分片鍵的值，找到對應的分片表(或分片庫)名稱并返回
return result;
}
}

其中 ComplexKeysShardingAlgorithm（接口）的源代碼為：

package org.apache.shardingsphere.api.sharding.complex;
......
public interface ComplexKeysShardingAlgorithm<T extends Comparable<?>> 
extends ShardingAlgorithm {
/**
* @param 所有可能的分片表(或分片庫)名稱
* @param 分片鍵的值
* @return 根據分片鍵的值，找到對應的分片表(或分片庫)名稱并返回
*/
Collection<String> doSharding(
Collection<String> availableTargetNames, 
ComplexKeysShardingValue<T> shardingValue
);
}

復合分片策略提供對 SQL 語句中的操作符=、>、<、>=、<=、IN 和 ETWEEN AND 的分片操作支持。

復合分片策略支持多分片鍵，例如對 t_order 表根據 order_id 和 user_id 分片。復合分片策略提供 ComplexKeysShardingAlgorithm（接口）分片算法。

我舉個例子幫助你理解以上兩段話的含義。以 t_order 為例，假如你使用 order_id 和 user_id 作為 t_order 的分片鍵，并設計了以下的分片策略：

策略一：設置 4 個分片
t_order.order_id % 2==0 && t_order.user_id % 2==0 的查詢分片到 t_order0
t_order.order_id % 2==0 && t_order.user_id % 2==1 的查詢分片到 t_order1
t_order.order_id % 2==1 && t_order.user_id % 2==0 的查詢分片到 t_order2
t_order.order_id % 2==1 && t_order.user_id % 2==1 的查詢分片到 t_order3
策略二：經過估算訂單不超過 60000 個、用戶不超過 1000 個，設置 4 個分片
t_order.order_id between 0 and 40000 && t_order.user_id between 0 and 500 的查詢分片到 t_order0
t_order.order_id between 0 and 40000 && t_order.user_id between 500 and 1000 的查詢分片到 t_order1
t_order.order_id between 40000 and 60000 && t_order.user_id between 0 and 500 的查詢分片到 t_order2
t_order.order_id between 40000 and 60000 && t_order.user_id between 500 and 1000 的查詢分片到 t_order3
......

那你就可以把以下三項：

1）分片鍵 order_id 和 user_id

2）描述以上分片策略內容的 ComplexKeysShardingAlgorithm（接口）的實現類

3）前兩項（即分片策略）的作用目標 t_order 表

寫到分片配置里（無論是通過配置 API 還是通過配置文件），那我就能知道如何去路由 SQL，即根據分片鍵的值，找到對應的分片表(或分片庫)。

有了這些配置，我就能幫你們透明處理如下 SQL 語句，不管實際的物理分片是怎樣的：

-- 注：使用 t_order.order_id、t_order.user_id 作為 t_order 表的分片鍵
SELECT o.* FROM t_order o WHERE o.order_id=10;
SELECT o.* FROM t_order o WHERE o.order_id IN (10, 11);
SELECT o.* FROM t_order o WHERE o.order_id > 10;
SELECT o.* FROM t_order o WHERE o.order_id <=11;
SELECT o.* FROM t_order o WHERE o.order_id BETWEEN 10 AND 12;
......
INSERT INTO t_order(order_id, user_id) VALUES (20, 1001);
......
DELETE FROM t_order o WHERE o.order_id=10;
DELETE FROM t_order o WHERE o.order_id IN (10, 11);
DELETE FROM t_order o WHERE o.order_id > 10;
DELETE FROM t_order o WHERE o.order_id <=11;
DELETE FROM t_order o WHERE o.order_id BETWEEN 10 AND 12;
......
UPDATE t_order o SET o.update_time=NOW WHERE o.order_id=10;
......
SELECT o.* FROM t_order o WHERE o.order_id=10 AND user_id=1001;
SELECT o.* FROM t_order o WHERE o.order_id IN (10, 11) AND user_id IN (......);
SELECT o.* FROM t_order o WHERE o.order_id > 10 AND user_id > 1000;
SELECT o.* FROM t_order o WHERE o.order_id <=11 AND user_id <=1000;
SELECT o.* FROM t_order o WHERE (o.order_id BETWEEN 10 AND 12) AND (o.user_id BETWEEN 1000 AND 2000);
......
INSERT INTO t_order(order_id, user_id) VALUES (21, 1002);
......
DELETE FROM t_order o WHERE o.order_id=10 AND user_id=1001;
DELETE FROM t_order o WHERE o.order_id IN (10, 11) AND user_id IN (......);
DELETE FROM t_order o WHERE o.order_id > 10 AND user_id > 1000;
DELETE FROM t_order o WHERE o.order_id <=11 AND user_id <=1000;
DELETE FROM t_order o WHERE (o.order_id BETWEEN 10 AND 12) AND (o.user_id BETWEEN 1000 AND 2000);
......
UPDATE t_order o SET o.update_time=NOW WHERE o.order_id=10 AND user_id=1001;
......

注：在《召喚我的方式》這一章，我給出了一段配置，這段配置表明先依照 user_id % 2 對 t_order 進行水平拆分（到不同的子庫），再依照 order_id % 2 對 t_order 進行水平拆分（到不同的子表）。但這并不是說使用了復合分片策略，而是使用了兩個兩個維度的標準分片策略。兩個維度，分別是數據源分片策略（DatabaseShardingStrategy）和表分片策略（TableShardingStrategy），且在數據源分片策略上使用 user_id 作為單分片鍵、在表分片策略上使用 order_id 作為單分片鍵。

三、Hint（翻譯為暗示） 分片策略

Hint 分片策略對應 HintShardingStrategy 這個 final class，同標準分片策略和符合分片策略的代碼類似，HintShardingStrategy 中包含一個 HintShardingAlgorithm 接口的實例，并調用它的 doSharding方法。你們要自己去實現這個 HintShardingAlgorithm 接口中的 doSharding方法，這樣我就能知道如何根據分片鍵的值，找到對應的分片表(或分片庫)。此處不在展示 HintShardingStrategy 和 HintShardingAlgorithm 的源碼。

Hint 分片策略是指通過 Hint 指定分片值而非從 SQL 中提取分片值的方式進行分片的策略。簡單來講就是我收到的 SQL 語句中不包含分片值（像上面給出的幾段 SQL 就是包含分片值的 SQL），但是工程師會通過我提供的 Java API 將分片值暗示給我，這樣我就知道怎樣路由 SQL 查詢到具體的分片了。就像下面這樣：

String sql="SELECT * FROM t_order";
try (
// HintManager 是使用“暗示”的工具，它會把暗示的分片值放入
// 當前線程上下文（ThreadLocal）中，這樣當前線程執行 SQL 的
// 時候就能獲取到分片值
HintManager hintManager=HintManager.getInstance;
Connection conn=dataSource.getConnection;
PreparedStatement pstmt=conn.prepareStatement(sql);
) {
hintManager.setDatabaseShardingValue(3);
try (ResultSet rs=pstmt.executeQuery) {
// 若 t_order 僅僅使用 order_id 作為分片鍵，則這里根據暗
// 示獲取了分片值，因此上面的 SQL 的實際執行效果相當于：
// SELECT * FROM t_order where order_id=3
while (rs.next) {
//...
} 
} 
}

四、不分片策略

對應 NoneShardingStrategy，這是一個 final class。由于我并不要求所有的表（或庫）都進行水平分片，因此當工程師要通過我執行對不分片表（或庫）的 SQL 查詢時，就要使用這個不分片策略。NoneShardingStrategy 的源碼為：

package org.apache.shardingsphere.core.strategy.route.none;
......
@Getter
public final classNoneShardingStrategyimplementsShardingStrategy{
private final Collection<String> shardingColumns=Collections.emptyList;
@Override
public Collection<String> doSharding(
// 所有可能的分片表(或分片庫)名稱
final Collection<String> availableTargetNames, 
// 分片鍵的值
final Collection<RouteValue> shardingValues, 
final ConfigurationProperties properties
) {
// 不需要任何算法，不進行任何邏輯處理，直接返回
// 所有可能的分片表(或分片庫)名稱
return availableTargetNames;
}
}

五、Inline 分片策略

Inline 分片策略，也叫做行表達式分片策略。Inline 分片策略對應 InlineShardingStrategy。Inline 分片策略是為用 Grovvy 表達式描述的分片算法準備的分片策略。文章開始展示的兩段配置中就使用了 Inline 分片策略。InlineShardingStrategy 把 Grovvy 表達式當做分片算法的實現，因此 HintShardingStrategy 中不包含算法域變量，這一點有別于 StandardShardingStrategy 等 final class。這里不再展示 InlineShardingStrategy 的源碼。

我知道，這段關于分片策略和分片算法的表述很難理解。不過我還是想讓你們明白，無論對某個邏輯表（或庫）進行怎樣的分片策略配置，這些策略不過都是在告訴我怎樣處理分片，也就是告訴我如何根據分片鍵的值，找到對應的分片表(或分片庫)。只不過我的創造者把這個簡單的過程翻出了很多花樣，也就是你們在上面看到的各種策略，以提供使用上的靈活性。

4.2.5. 綁定表

指分片規則一致的主表和子表。例如 t_order 是主表，存儲訂單的基本信息；t_order_item 是子表，存儲訂單中的商品和價格明細。若兩張表均按照 order_id 分片，并且配置了兩個表之間的綁定關系，則此兩張表互為綁定表。綁定表之間的多表關聯查詢不會出現笛卡爾積關聯，關聯查詢效率將大大提升。舉例說明，如果 SQL 為：

SELECT i.* FROM t_order o JOIN t_order_item i ON o.order_id=i.order_id WHERE o.order_id IN (10, 11);

在不配置綁定表關系時，假設分片鍵 order_id 將數值 10 路由至第 0 片，將數值 11 路由至第 1 片，那么路由后的 SQL 應該為 4 條，它們呈現為笛卡爾積，這種情況是我最不愿意處理的，我要考慮所有可能的分組合，它的工作量實在太大了：

SELECT i.* FROM t_order0 o JOIN t_order_item0 i ON o.order_id=i.order_id WHERE o.order_id IN (10, 11);
SELECT i.* FROM t_order0 o JOIN t_order_item1 i ON o.order_id=i.order_id WHERE o.order_id IN (10, 11);
SELECT i.* FROM t_order1 o JOIN t_order_item0 i ON o.order_id=i.order_id WHERE o.order_id IN (10, 11);
SELECT i.* FROM t_order1 o JOIN t_order_item1 i ON o.order_id=i.order_id WHERE o.order_id IN (10, 11);

而在配置綁定表關系后，路由的 SQL 只有 2 條：

SELECT i.* FROM t_order0 o JOIN t_order_item0 i ON o.order_id=i.order_id WHERE o.order_id IN (10, 11);
SELECT i.* FROM t_order1 o JOIN t_order_item1 i ON o.order_id=i.order_id WHERE o.order_id IN (10, 11);

而我也提供了這種綁定關系配置的 API 和配置項，例如在 properties 配置文件中可以這么寫：

# 設置綁定表
sharding.jdbc.config.sharding.binding-tables=t_order, t_order_item

4.3. 我處理 SQL 的過程

我是 Sharding-JDBC，我是水平分片世界的神。我的職責是透明化水平分庫分表所帶來的影響，讓使用方盡量像使用一個數據庫一樣使用水平分片之后的數據庫集群，或者像使用一個數據表一樣使用水平分片之后的數據表。

我的法力，來源于我的創造者為我設計的內核，它把 SQL 語句的處理分成了 SQL 解析=>SQL 路由=> SQL 改寫=> SQL 執行=> 結果歸并五個主要流程。

當一個應用服務器節點將一個面向邏輯表編寫的查詢 SQL 交給我之后，我要做下面幾件事：

1）SQL 解析（由我內核中的解析引擎完成）：先通過詞法解析器將邏輯 SQL 拆分為一個個不可再分的單詞，再使用語法解析器對 SQL 進行理解，并最終提煉出解析上下文。

2）SQL 路由（由我內核中的路由引擎完成）：根據解析上下文匹配用戶配置的分片策略（關于用戶配置的分片策略，我后文會慢慢解釋），并生成路由路徑，路由路徑指示了 SQL 最終要到哪些分片去執行。

3）SQL 改寫（由我內核中的改寫引擎完成）：將 面向邏輯表 SQL 改寫為在真實數據庫中可以正確執行的語句（邏輯 SQL 到物理 SQL 的映射）。

4）SQL 執行（由我內核中的執行引擎完成）：通過多線程執行器異步執行路由和改寫之后得到的 SQL 語句。

5）結果歸并（由我內核中的歸并引擎完成）：將多個執行結果集歸并以便于通過統一的 JDBC 接口輸出。

4.3.1. SQL 解析

SQL 解析 SQL 解析分為詞法解析和語法解析。

我的解析引擎先通過詞法解析器將這句 SQL 拆分為一個個不可再分的單詞，再使用語法解析器對 SQL 進行理解，并最終提煉出解析上下文。解析上下文包括表、選擇項、排序項、分組項、聚合函數、分頁信息、查詢條件以及可能需要修改的占位符的標記。簡單來說就是我要理解這句 SQL，明白它的結構和意圖。所幸，SQL 是一個語法簡單的語言，SQL 解析這件事情并不復雜。

我先使用解析引擎的詞法解析器用于將 SQL 拆解為不可再分的原子符號，我把它們叫做 Token，并將其歸類為關鍵字、表達式、字面量、操作符，再使用解析引擎的語法解析器將 SQL 轉換為抽象語法樹。

例如，以下 SQL：

SELECT id, name FROM t_user WHERE status='ACTIVE' AND age > 18

被我的詞法解析器和語法解析器解析之后得到的抽象語法樹為：

在上圖中，為了便于理解，抽象語法樹中的關鍵字和操作符的 Token 用綠?表示，字面量的 Token 用紅?表示，灰?表示需要進一步拆分。

最后，我通過對抽象語法樹的遍歷去提煉分片所需的上下文，并標記有可能需要改寫的位置。供分片使用的解析上下文包含查詢選擇項（Select Items）、表信息（Table）、分片條件（Sharding Condition）、自增主鍵信息（Auto increment Primary Key）、排序信息（Order By）、分組信息（Group By）以及分頁信息（Limit、Rownum、Top）。

SQL 解析是下面的