1.順序索引
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? part1:主索引
1.主索引：如果包含記錄的文件按照某個(gè)搜索碼的順序排列，那么該搜索碼對應(yīng)的索引稱為主索引，主索引也叫做聚合索引
這個(gè)例子中，第一列的branch-name是搜索碼，而記錄按照該搜索碼的順序存放
2.順序與文件記錄中的物理順序不同的索引叫做輔助索引或者非聚集索引
3.稠密索引：文件中搜索碼的每一個(gè)值都有一個(gè)索引記錄，索引記錄包括搜索碼值以及指向該搜索碼值的第一個(gè)記錄的指針。
4.稀疏索引：只為搜索碼的某些值建立索引記錄，也包括一個(gè)搜索碼值和指向具有該搜索碼值的第一個(gè)數(shù)據(jù)記錄的指針。
上圖是為account文件建立的稠密索引和稀疏索引，假如要找Perryridge，稠密索引可以順著指針直接從文件中找到Perryridge的第一條記錄，處理完這條，可以根據(jù)這條記錄中的指針找到按照搜索碼排在下一條的記錄，直到找到redwood這一條記錄停止。如果是稀疏索引找的話，“mianus”是Perryridge前面的最后一個(gè)索引項(xiàng)，沿著這一指針找到指向的記錄，接著順序讀入，直到找到第一個(gè)Perryridge記錄。
稠密索引可以更快的定位一個(gè)記錄，稀疏索引所占空間小，并且插入和刪除的時(shí)候維護(hù)開銷也比較小。
5.多級索引：在外層索引上用二分法找到不大于所需搜索碼值的最大搜索碼值所對應(yīng)的記錄，指針指向一個(gè)內(nèi)層索引塊，對這一塊進(jìn)行掃描，直到找到不大于所需搜索碼值的最大搜索碼值所對應(yīng)的記錄
6.索引的更新：（一級索引）
刪除：首先找到要?jiǎng)h除的記錄，如果要?jiǎng)h除的搜索碼值在文件中是唯一的，那么該搜索碼值要從索引中刪除。 對稀疏索引而言，如果被刪除搜索碼值在索引中有索引項(xiàng)，可以通過用下一搜索碼值替代這個(gè)索引項(xiàng)來實(shí)現(xiàn)對搜索碼值的刪除，如果下一個(gè)搜索碼值已經(jīng)有索引項(xiàng)，那么該索引項(xiàng)就應(yīng)該刪除而不是替代。
插入：索引是稠密的 ，該搜索碼不在索引中，把它加入該索引中。如果索引是為每個(gè)塊保存一個(gè)索引項(xiàng)的稀疏索引，只要沒有新塊產(chǎn)生，索引就不需要做改動，產(chǎn)生新塊的條件下，新塊中的第一個(gè)搜索碼值插入索引
7.輔助索引
如果輔助索引的搜索碼不是一個(gè)候選碼，輔助索引必須包含指向每一條記錄的指針，但是如果是主索引，那么可以僅僅指出各個(gè)搜索碼值的第一個(gè)記錄，因?yàn)橹魉饕前错樞虼娣诺?。所以輔助索引必須是稠密的，必須對每個(gè)搜索碼值都有一個(gè)索引項(xiàng)且對應(yīng)文件中的每個(gè)記錄都有一個(gè)指針。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?part2 b+樹索引文件
1.索引組織文件的缺點(diǎn)：隨著文件的增大，索引查找性能和數(shù)據(jù)順序掃描性能都會下降。一些索引結(jié)構(gòu)能在有數(shù)據(jù)插入和刪除的情況下保持其有效性，b+樹索引結(jié)構(gòu)就是其中使用最廣泛的一個(gè)。
2.結(jié)構(gòu)：每個(gè)葉結(jié)點(diǎn)到根的路徑長度都相同；非葉結(jié)點(diǎn)至少包含[n／2]個(gè)指針，最多n個(gè)；葉結(jié)點(diǎn)包含值的個(gè)數(shù)最少為[（n-1）/2]；根結(jié)點(diǎn)包含的指針數(shù)可以小于[n/2]，但是除非整棵樹之友一個(gè)結(jié)點(diǎn)，否則根必須至少包含兩個(gè)指針
指針pi 指向具有搜索碼值ki的一個(gè)文件記錄活著一個(gè)指針桶，桶中的每個(gè)指針指向具有搜索碼值ki的一個(gè)文件記錄，指針桶只在搜索碼不是主碼且文件不按搜索碼順序存放時(shí)才使用。
圖11-7： n=3，搜索碼是branch-name， 葉結(jié)點(diǎn)的指針直接指向文件
結(jié)點(diǎn)的指針數(shù)稱為該節(jié)點(diǎn)的扇出
3.特點(diǎn)：增加文件插入和刪除處理的時(shí)間開銷和空間開銷，但是這種開銷即使對于更新頻率較高的文件來說也可以接受因?yàn)樗軌虮苊馕募亟M的開銷。
4.查詢：需要遍歷樹中從根到某個(gè)葉結(jié)點(diǎn)的一條路徑
5.更新：
如果結(jié)點(diǎn)必須分裂：那么規(guī)則是n個(gè)值（葉結(jié)點(diǎn)原有的n-1個(gè)加上新插入的值）分成兩組，前[n/2]個(gè)放在原來的結(jié)點(diǎn)中，eg：3分成2，1，剩下的放在新結(jié)點(diǎn)中，在結(jié)點(diǎn)分裂后，我們必須將這個(gè)新結(jié)點(diǎn)加入b+樹結(jié)構(gòu)中，
假如我們要在上面的11-8中加入clearview， 分裂后，新結(jié)點(diǎn)的最小搜索碼是downtown，把這個(gè)搜索碼值插入到被分裂結(jié)點(diǎn)的父結(jié)點(diǎn)中。
刪除上圖的downtown：
總的來說。為了刪除一個(gè)值，結(jié)點(diǎn)太小的話，我們從父結(jié)點(diǎn)中把它刪除。這個(gè)刪除導(dǎo)致刪除算法的遞歸應(yīng)用，直到到達(dá)樹的根結(jié)點(diǎn)或父結(jié)點(diǎn)在刪除后足夠滿或產(chǎn)生指針的重新分布。
6.b+樹文件組織
b+數(shù)結(jié)構(gòu)不僅用做索引，同時(shí)也是文件中記錄的組織者
在b+樹文件組織中，樹葉結(jié)點(diǎn)中存儲的是記錄而不是指向記錄的指針。由于記錄通常比指針大，一個(gè)葉結(jié)點(diǎn)中能存儲的記錄數(shù)目要比非葉結(jié)點(diǎn)中能存儲的指針數(shù)目少，但葉結(jié)點(diǎn)仍然要求至少是半滿的。
改善b+樹的利用率，這個(gè)技術(shù)可以同時(shí)用于根結(jié)點(diǎn)和葉結(jié)點(diǎn)：
在插入時(shí)，如果結(jié)點(diǎn)已經(jīng)滿了，盡力把它的一些項(xiàng)重新分配到與他相鄰的結(jié)點(diǎn)，以給新項(xiàng)騰出空間。如果因?yàn)橄噜徑Y(jié)點(diǎn)已滿而導(dǎo)致這一重分配失敗，我們就要分裂結(jié)點(diǎn)，并在由原始結(jié)點(diǎn)分裂所產(chǎn)生的兩個(gè)結(jié)點(diǎn)和一個(gè)相鄰結(jié)點(diǎn)之間均勻的分配所有項(xiàng)。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?part3：b樹索引文件
主要區(qū)別在于b樹去除了搜索碼值存儲中的冗余。b樹允許搜索碼值只出現(xiàn)一次，由于非葉結(jié)點(diǎn)中出現(xiàn)的搜索碼值不在b樹中其他任何地方出現(xiàn)，我們不得不為非葉結(jié)點(diǎn)中的每個(gè)搜索碼添加一個(gè)指針。附加的指針指向文件記錄或相應(yīng)搜索碼值對應(yīng)的桶。
b樹中進(jìn)行一次查找所訪問的結(jié)點(diǎn)數(shù)取決于搜索碼的位置，刪除更加復(fù)雜，在空間上的優(yōu)勢對于大的索引來講意義不大。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? part4:靜態(tài)散列
順序文件組織中的一個(gè)缺點(diǎn)就是我們必須訪問索引結(jié)構(gòu)來定位數(shù)據(jù)，或者使用二分法搜索，這將導(dǎo)致過多的io操作?；谏⒘械奈募M織使我們能夠避免訪問索引結(jié)構(gòu)。
1.散列文件組織
通過計(jì)算所需記錄搜索碼上的一個(gè)函數(shù)直接獲得包含該記錄的磁盤塊地址
桶表示能存儲一條或者多條記錄的一個(gè)存儲單位，通常一個(gè)桶就是一個(gè)磁盤塊，但也可能小于或者大于一個(gè)磁盤塊。
K表示所有搜索碼的集合，B表示所有桶地址的集合，散列函數(shù)h就是一個(gè)從K到B的函數(shù)
為了插入一個(gè)搜索碼值為Kt的記錄，就計(jì)算h（Kt）來得到存放該記錄的桶的地址。
查找，假定k5和k7有相同的散列值，h(k5)=h(k7),如果我們執(zhí)行對k5的查找，則桶h(k5)包含搜索碼是k5或者k7的記錄，因此，必須查找桶中每條記錄的搜索碼值，以確定該記錄是否是我們要查找的記錄。
2.散列函數(shù)
理想情況是將存儲的碼均勻的分布到所有桶中，使每個(gè)桶中含有相同數(shù)目的記錄。
3.桶溢出控制
假設(shè)插入一個(gè)記錄時(shí)，記錄映射的桶中具有存儲記錄的空間，如果桶中沒有足夠的空間，就會發(fā)生桶溢出。桶溢出的原因：
??桶不足
??偏斜。某些桶分配到的記錄比較多（多個(gè)記錄有相同的搜索碼+散列函數(shù)造成搜索碼的分布不均）
可以使用溢出桶來處理問題。
4. 散列索引
散列不僅可以用于文件的組織，還可以用于索引結(jié)構(gòu)的創(chuàng)建，散列索引將搜索碼及相應(yīng)指針組織稱散列文件結(jié)構(gòu)。
散列函數(shù)是計(jì)算賬號各位數(shù)字之和之后模7.
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?part5:動態(tài)散列法
1.靜態(tài)散列的問題：大多數(shù)數(shù)據(jù)庫都會隨時(shí)間而變大，如果要在這樣的數(shù)據(jù)庫上使用靜態(tài)散列，有三種選擇
a.根據(jù)當(dāng)前文件大小選擇散列函數(shù)，這種選擇會使性能隨數(shù)據(jù)庫增大而下降
b.根據(jù)將來某個(gè)時(shí)刻文件的大小選擇散列函數(shù)，盡管這樣可以避免性能下降，但是初始時(shí)會造成相當(dāng)大的空間浪費(fèi)
c.隨著文件增大，周期性對散列結(jié)構(gòu)進(jìn)行重組。復(fù)雜耗時(shí)
可擴(kuò)充散列的動態(tài)散列技術(shù)：
桶地址表上方的i表明散列值h(k)中有i位需要用來決定對應(yīng)于k的桶，
舉個(gè)??：
