1.順序索引
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? part1:主索引
1.主索引：如果包含記錄的文件按照某個搜索碼的順序排列虐块，那么該搜索碼對應的索引稱為主索引，主索引也叫做聚合索引
這個例子中，第一列的branch-name是搜索碼荤西，而記錄按照該搜索碼的順序存放
2.順序與文件記錄中的物理順序不同的索引叫做輔助索引或者非聚集索引
3.稠密索引：文件中搜索碼的每一個值都有一個索引記錄伟桅，索引記錄包括搜索碼值以及指向該搜索碼值的第一個記錄的指針。
4.稀疏索引：只為搜索碼的某些值建立索引記錄越驻，也包括一個搜索碼值和指向具有該搜索碼值的第一個數(shù)據(jù)記錄的指針汁政。
上圖是為account文件建立的稠密索引和稀疏索引，假如要找Perryridge缀旁，稠密索引可以順著指針直接從文件中找到Perryridge的第一條記錄记劈，處理完這條，可以根據(jù)這條記錄中的指針找到按照搜索碼排在下一條的記錄诵棵，直到找到redwood這一條記錄停止抠蚣。如果是稀疏索引找的話，“mianus”是Perryridge前面的最后一個索引項履澳，沿著這一指針找到指向的記錄嘶窄，接著順序讀入，直到找到第一個Perryridge記錄距贷。
稠密索引可以更快的定位一個記錄柄冲，稀疏索引所占空間小，并且插入和刪除的時候維護開銷也比較小忠蝗。
5.多級索引：在外層索引上用二分法找到不大于所需搜索碼值的最大搜索碼值所對應的記錄现横，指針指向一個內層索引塊，對這一塊進行掃描，直到找到不大于所需搜索碼值的最大搜索碼值所對應的記錄
6.索引的更新：（一級索引）
刪除：首先找到要刪除的記錄戒祠，如果要刪除的搜索碼值在文件中是唯一的骇两，那么該搜索碼值要從索引中刪除。 對稀疏索引而言姜盈，如果被刪除搜索碼值在索引中有索引項低千，可以通過用下一搜索碼值替代這個索引項來實現(xiàn)對搜索碼值的刪除，如果下一個搜索碼值已經(jīng)有索引項馏颂，那么該索引項就應該刪除而不是替代示血。
插入：索引是稠密的 ，該搜索碼不在索引中救拉，把它加入該索引中难审。如果索引是為每個塊保存一個索引項的稀疏索引，只要沒有新塊產生亿絮，索引就不需要做改動告喊，產生新塊的條件下，新塊中的第一個搜索碼值插入索引
7.輔助索引
如果輔助索引的搜索碼不是一個候選碼壹无，輔助索引必須包含指向每一條記錄的指針葱绒，但是如果是主索引，那么可以僅僅指出各個搜索碼值的第一個記錄斗锭，因為主索引是按順序存放的地淀。所以輔助索引必須是稠密的，必須對每個搜索碼值都有一個索引項且對應文件中的每個記錄都有一個指針岖是。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?part2 b+樹索引文件
1.索引組織文件的缺點：隨著文件的增大帮毁，索引查找性能和數(shù)據(jù)順序掃描性能都會下降。一些索引結構能在有數(shù)據(jù)插入和刪除的情況下保持其有效性豺撑，b+樹索引結構就是其中使用最廣泛的一個烈疚。
2.結構：每個葉結點到根的路徑長度都相同；非葉結點至少包含[n／2]個指針聪轿，最多n個爷肝；葉結點包含值的個數(shù)最少為[（n-1）/2]；根結點包含的指針數(shù)可以小于[n/2]陆错，但是除非整棵樹之友一個結點灯抛，否則根必須至少包含兩個指針
指針pi 指向具有搜索碼值ki的一個文件記錄活著一個指針桶，桶中的每個指針指向具有搜索碼值ki的一個文件記錄音瓷，指針桶只在搜索碼不是主碼且文件不按搜索碼順序存放時才使用对嚼。
圖11-7： n=3，搜索碼是branch-name绳慎， 葉結點的指針直接指向文件
結點的指針數(shù)稱為該節(jié)點的扇出
3.特點：增加文件插入和刪除處理的時間開銷和空間開銷纵竖，但是這種開銷即使對于更新頻率較高的文件來說也可以接受因為他能夠避免文件重組的開銷漠烧。
4.查詢：需要遍歷樹中從根到某個葉結點的一條路徑
5.更新：
如果結點必須分裂：那么規(guī)則是n個值（葉結點原有的n-1個加上新插入的值）分成兩組，前[n/2]個放在原來的結點中靡砌，eg：3分成2已脓，1，剩下的放在新結點中通殃，在結點分裂后摆舟，我們必須將這個新結點加入b+樹結構中，
假如我們要在上面的11-8中加入clearview邓了， 分裂后，新結點的最小搜索碼是downtown媳瞪，把這個搜索碼值插入到被分裂結點的父結點中骗炉。
刪除上圖的downtown：
總的來說。為了刪除一個值蛇受，結點太小的話句葵，我們從父結點中把它刪除。這個刪除導致刪除算法的遞歸應用兢仰，直到到達樹的根結點或父結點在刪除后足夠滿或產生指針的重新分布乍丈。
6.b+樹文件組織
b+數(shù)結構不僅用做索引，同時也是文件中記錄的組織者
在b+樹文件組織中把将，樹葉結點中存儲的是記錄而不是指向記錄的指針轻专。由于記錄通常比指針大，一個葉結點中能存儲的記錄數(shù)目要比非葉結點中能存儲的指針數(shù)目少察蹲，但葉結點仍然要求至少是半滿的请垛。
改善b+樹的利用率，這個技術可以同時用于根結點和葉結點：
在插入時洽议，如果結點已經(jīng)滿了宗收，盡力把它的一些項重新分配到與他相鄰的結點，以給新項騰出空間亚兄。如果因為相鄰結點已滿而導致這一重分配失敗混稽，我們就要分裂結點，并在由原始結點分裂所產生的兩個結點和一個相鄰結點之間均勻的分配所有項审胚。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?part3：b樹索引文件
主要區(qū)別在于b樹去除了搜索碼值存儲中的冗余匈勋。b樹允許搜索碼值只出現(xiàn)一次，由于非葉結點中出現(xiàn)的搜索碼值不在b樹中其他任何地方出現(xiàn)菲盾，我們不得不為非葉結點中的每個搜索碼添加一個指針颓影。附加的指針指向文件記錄或相應搜索碼值對應的桶。
b樹中進行一次查找所訪問的結點數(shù)取決于搜索碼的位置懒鉴，刪除更加復雜诡挂，在空間上的優(yōu)勢對于大的索引來講意義不大碎浇。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? part4:靜態(tài)散列
順序文件組織中的一個缺點就是我們必須訪問索引結構來定位數(shù)據(jù)，或者使用二分法搜索璃俗，這將導致過多的io操作奴璃。基于散列的文件組織使我們能夠避免訪問索引結構城豁。
1.散列文件組織
通過計算所需記錄搜索碼上的一個函數(shù)直接獲得包含該記錄的磁盤塊地址
桶表示能存儲一條或者多條記錄的一個存儲單位苟穆，通常一個桶就是一個磁盤塊，但也可能小于或者大于一個磁盤塊唱星。
K表示所有搜索碼的集合雳旅，B表示所有桶地址的集合，散列函數(shù)h就是一個從K到B的函數(shù)
為了插入一個搜索碼值為Kt的記錄间聊，就計算h（Kt）來得到存放該記錄的桶的地址攒盈。
查找，假定k5和k7有相同的散列值哎榴，h(k5)=h(k7),如果我們執(zhí)行對k5的查找型豁，則桶h(k5)包含搜索碼是k5或者k7的記錄，因此尚蝌，必須查找桶中每條記錄的搜索碼值迎变，以確定該記錄是否是我們要查找的記錄。
2.散列函數(shù)
理想情況是將存儲的碼均勻的分布到所有桶中飘言，使每個桶中含有相同數(shù)目的記錄衣形。
3.桶溢出控制
假設插入一個記錄時，記錄映射的桶中具有存儲記錄的空間姿鸿，如果桶中沒有足夠的空間泵喘，就會發(fā)生桶溢出。桶溢出的原因：
??桶不足
??偏斜般妙。某些桶分配到的記錄比較多（多個記錄有相同的搜索碼+散列函數(shù)造成搜索碼的分布不均）
可以使用溢出桶來處理問題纪铺。
4. 散列索引
散列不僅可以用于文件的組織，還可以用于索引結構的創(chuàng)建碟渺，散列索引將搜索碼及相應指針組織稱散列文件結構鲜锚。
散列函數(shù)是計算賬號各位數(shù)字之和之后模7.
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?part5:動態(tài)散列法
1.靜態(tài)散列的問題：大多數(shù)數(shù)據(jù)庫都會隨時間而變大，如果要在這樣的數(shù)據(jù)庫上使用靜態(tài)散列苫拍，有三種選擇
a.根據(jù)當前文件大小選擇散列函數(shù)芜繁，這種選擇會使性能隨數(shù)據(jù)庫增大而下降
b.根據(jù)將來某個時刻文件的大小選擇散列函數(shù)，盡管這樣可以避免性能下降绒极，但是初始時會造成相當大的空間浪費
c.隨著文件增大骏令，周期性對散列結構進行重組。復雜耗時
可擴充散列的動態(tài)散列技術：
桶地址表上方的i表明散列值h(k)中有i位需要用來決定對應于k的桶垄提，
舉個??：
