順序查找
（線性查找）
1.一般線性表的順序查找
引入哨兵酬滤，使得循環(huán)時(shí)不必判斷是否越界
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)，即有動(dòng)態(tài)結(jié)構(gòu)，又適于快速查找饱搏。
基本思想：將查找表分為若干子塊，塊內(nèi)無序，塊間有序田轧。前一個(gè)塊中的最大關(guān)鍵字小于后一塊中所有記錄的關(guān)鍵字。建立一個(gè)索引表鞍恢，索引表中的每個(gè)元素含有各塊的最大關(guān)鍵字和各塊中的第一個(gè)元素的地址傻粘，索引表按關(guān)鍵字有序排序。
B樹
（多路平衡查找樹）
一棵m階B樹或?yàn)榭諛浒锏簦驗(yàn)闈M足如下特性的m叉樹
1.樹中每個(gè)節(jié)點(diǎn)最多有m課子樹（m-1個(gè)關(guān)鍵字）
2.若根節(jié)點(diǎn)不是終端節(jié)點(diǎn)弦悉，則至少有兩棵子樹
3.除根節(jié)點(diǎn)外的所有非葉節(jié)點(diǎn)至少有?m/2?棵子樹（?m/2?-1個(gè)關(guān)鍵字）
4.非葉結(jié)點(diǎn)的結(jié)構(gòu)為
________________________________
| n | P0 | K1 | P1 | K2 | P2 |......| Kn | Pn|
————————————————————————————————
n個(gè)關(guān)鍵字，n+1個(gè)指針
Ki為關(guān)鍵字且按順序排列
Pi為指向子樹的指針
Pi-1所指子樹的值均小于Ki蟆炊，Pi所指子樹的指均大于Ki
n為結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(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樹常存儲(chǔ)在磁盤上盅称，因此前一個(gè)查找操作是在磁盤上進(jìn)行的肩祥，后一個(gè)是在內(nèi)存中進(jìn)行。
查找到某個(gè)節(jié)點(diǎn)后缩膝，先在有序表中進(jìn)行查找混狠，若找到則查找成功，否則按照對(duì)應(yīng)的指針信息到所指的子樹中去查找疾层，查找到葉結(jié)點(diǎn)時(shí)将饺，則說明樹中沒有對(duì)應(yīng)關(guān)鍵字，查找失敗痛黎。
B樹的插入
1.定位：利用B樹查找法予弧，找出插入該關(guān)鍵字的最低層中的某個(gè)非葉節(jié)點(diǎn)
2.插入：插入后節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)小于m則可直接插入，否則對(duì)結(jié)點(diǎn)進(jìn)行分裂
3.分裂：取一個(gè)新結(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)個(gè)數(shù)大于m-1致讥，則繼續(xù)分裂直至這個(gè)過程到根節(jié)點(diǎn)為止，此時(shí)會(huì)導(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)對(duì)應(yīng)關(guān)鍵字加到所在節(jié)點(diǎn)中请契，兄弟節(jié)點(diǎn)中的一個(gè)關(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)中對(duì)應(yīng)的那個(gè)關(guān)鍵字加到所在子節(jié)點(diǎn)與其某個(gè)兄弟節(jié)點(diǎn)合并后的節(jié)點(diǎn)中
合并過程會(huì)導(dǎo)致父節(jié)點(diǎn)中關(guān)鍵字減少爽锥，若是根節(jié)點(diǎn)個(gè)數(shù)減少到0，則刪除根節(jié)點(diǎn)授舟，將合并后的節(jié)點(diǎn)作為新的根救恨。若非根節(jié)點(diǎn)減少到?m/2?-2，則又要與它自己的兄弟節(jié)點(diǎn)進(jìn)行調(diào)整或合并操作释树。
圖解
http://www.reibang.com/p/a858bb15cbf0
B+樹
1.樹中每個(gè)節(jié)點(diǎn)最多有m課子樹
2.若根節(jié)點(diǎn)不是終端節(jié)點(diǎn)肠槽，則至少有兩棵子樹，除根節(jié)點(diǎn)外的所有非葉節(jié)點(diǎn)至少有?m/2?棵子樹
4.結(jié)點(diǎn)的子樹個(gè)數(shù)與關(guān)鍵字個(gè)數(shù)相同
5.所有葉結(jié)點(diǎn)包含全部關(guān)鍵字及指向相應(yīng)記錄的指針奢啥，葉結(jié)點(diǎn)中將關(guān)鍵字按大小順序排列秸仙，并且相鄰葉結(jié)點(diǎn)按大小順序相互鏈接起來
6.所有分支節(jié)點(diǎn)中僅包含它的各個(gè)子節(jié)點(diǎn)中關(guān)鍵字的最大值
兩種查找方式
