順序查找
（線性查找）
1.一般線性表的順序查找
引入哨兵，使得循環(huán)時不必判斷是否越界
ST.elem[0]=key;
for(i=ST.TableLen;ST.elem[i]!=key;--i);
return i;
ASL成功=(n+1)/2
ASL失敗=n+1
2.有序表的順序查找
查找判定樹
ASL成功=(n+1)/2
ASL失敗=n/2+n/(n+1)
折半查找
（二分查找）
僅適用于有序的順序表
int Binary_Search(SeqList L, ElemType key)
{
int low=0, high=L.TableLen-1, mid);
while(low<=high){
mid=(low+high)/2;
if(L.elem[mid]==key)
return mid;
else if(L.elem[mid]>key)
high=mid-1;
else
low=mid+1;
}
return -1;
}
判定樹
ASL成功=log2(n+1)-1
分塊查找
（索引順序查找）
吸取了順序查找和折半查找各自的優(yōu)點(diǎn)，即有動態(tài)結(jié)構(gòu)，又適于快速查找。
基本思想：將查找表分為若干子塊，塊內(nèi)無序，塊間有序。前一個塊中的最大關(guān)鍵字小于后一塊中所有記錄的關(guān)鍵字。建立一個索引表，索引表中的每個元素含有各塊的最大關(guān)鍵字和各塊中的第一個元素的地址，索引表按關(guān)鍵字有序排序。
B樹
（多路平衡查找樹）
一棵m階B樹或?yàn)榭諛?，或?yàn)闈M足如下特性的m叉樹
1.樹中每個節(jié)點(diǎn)最多有m課子樹（m-1個關(guān)鍵字）
2.若根節(jié)點(diǎn)不是終端節(jié)點(diǎn)，則至少有兩棵子樹
3.除根節(jié)點(diǎn)外的所有非葉節(jié)點(diǎn)至少有?m/2?棵子樹（?m/2?-1個關(guān)鍵字）
4.非葉結(jié)點(diǎn)的結(jié)構(gòu)為
________________________________
| n | P0 | K1 | P1 | K2 | P2 |......| Kn | Pn|
————————————————————————————————
n個關(guān)鍵字，n+1個指針
Ki為關(guān)鍵字且按順序排列
Pi為指向子樹的指針
Pi-1所指子樹的值均小于Ki，Pi所指子樹的指均大于Ki
n為結(jié)點(diǎn)中關(guān)鍵字的個數(shù)
5.所有葉節(jié)點(diǎn)都出現(xiàn)在同一層次上，且不帶信息，實(shí)際不存在指針為空
B樹的高度
磁盤的存取次數(shù)
（不包括最后的不帶信息葉結(jié)點(diǎn)那層）
B樹的查找
1.在B樹中找結(jié)點(diǎn)
2.在結(jié)點(diǎn)內(nèi)找關(guān)鍵字
由于B樹常存儲在磁盤上，因此前一個查找操作是在磁盤上進(jìn)行的，后一個是在內(nèi)存中進(jìn)行。
查找到某個節(jié)點(diǎn)后，先在有序表中進(jìn)行查找，若找到則查找成功，否則按照對應(yīng)的指針信息到所指的子樹中去查找，查找到葉結(jié)點(diǎn)時，則說明樹中沒有對應(yīng)關(guān)鍵字，查找失敗。
B樹的插入
1.定位：利用B樹查找法，找出插入該關(guān)鍵字的最低層中的某個非葉節(jié)點(diǎn)
2.插入：插入后節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)小于m則可直接插入，否則對結(jié)點(diǎn)進(jìn)行分裂
3.分裂：取一個新結(jié)點(diǎn)，在插入key后的原節(jié)點(diǎn)從中間位置將其中的關(guān)鍵字分為兩部分，左邊的部分留在原節(jié)點(diǎn)，右邊的部分去新結(jié)點(diǎn)，中間位置（m/2向上取整）的節(jié)點(diǎn)插入到父節(jié)點(diǎn)，若導(dǎo)致父節(jié)點(diǎn)個數(shù)大于m-1，則繼續(xù)分裂直至這個過程到根節(jié)點(diǎn)為止，此時會導(dǎo)致B樹高度增加1
pic
B樹的刪除
將被刪除關(guān)鍵字Ki與它的左或右子節(jié)點(diǎn)中最相近的關(guān)鍵字Ki'替代它，再遞歸刪除Ki'
有以下幾種情況
1.若其所在節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)大于?m/2?-1，則直接刪除
2.若其所在節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)等于?m/2?-1，兄弟節(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)大于?m/2?-1，父節(jié)點(diǎn)對應(yīng)關(guān)鍵字加到所在節(jié)點(diǎn)中，兄弟節(jié)點(diǎn)中的一個關(guān)鍵字移到父節(jié)點(diǎn)
3.若其所在節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)等于?m/2?-1，左右兄弟節(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)也均等于?m/2?-1，就把父節(jié)點(diǎn)中對應(yīng)的那個關(guān)鍵字加到所在子節(jié)點(diǎn)與其某個兄弟節(jié)點(diǎn)合并后的節(jié)點(diǎn)中
合并過程會導(dǎo)致父節(jié)點(diǎn)中關(guān)鍵字減少，若是根節(jié)點(diǎn)個數(shù)減少到0，則刪除根節(jié)點(diǎn)，將合并后的節(jié)點(diǎn)作為新的根。若非根節(jié)點(diǎn)減少到?m/2?-2，則又要與它自己的兄弟節(jié)點(diǎn)進(jìn)行調(diào)整或合并操作。
圖解
http://www.itdecent.cn/p/a858bb15cbf0
B+樹
1.樹中每個節(jié)點(diǎn)最多有m課子樹
2.若根節(jié)點(diǎn)不是終端節(jié)點(diǎn)，則至少有兩棵子樹，除根節(jié)點(diǎn)外的所有非葉節(jié)點(diǎn)至少有?m/2?棵子樹
4.結(jié)點(diǎn)的子樹個數(shù)與關(guān)鍵字個數(shù)相同
5.所有葉結(jié)點(diǎn)包含全部關(guān)鍵字及指向相應(yīng)記錄的指針，葉結(jié)點(diǎn)中將關(guān)鍵字按大小順序排列，并且相鄰葉結(jié)點(diǎn)按大小順序相互鏈接起來
6.所有分支節(jié)點(diǎn)中僅包含它的各個子節(jié)點(diǎn)中關(guān)鍵字的最大值
兩種查找方式
