靜態(tài)索引結(jié)構(gòu)動態(tài)索引結(jié)構(gòu)散列可擴充散列.ppt

靜態(tài)索引結(jié)構(gòu) 動態(tài)索引結(jié)構(gòu) 散列 可擴充散列,第十章 索引與散列,靜態(tài)索引結(jié)構(gòu),示例：有一個存放職工信息的數(shù)據(jù)表, 每一 個職工對象有近 1k 字節(jié)的信息, 正好占據(jù)一 個頁塊的存儲空間。,當數(shù)據(jù)對象個數(shù) n 很大時, 如果用無序表形式的靜態(tài)搜索結(jié)構(gòu)存儲, 采用順序搜索, 則搜索效率極低。如果采用有序表存儲形式的靜態(tài)搜索結(jié)構(gòu), 則插入新記錄進行排序, 時間開銷也很可觀。這時可采用索引方法來實現(xiàn)存儲和搜索。,線性索引 (Linear Index List),100 140 180 220 260 300 340 380,key addr 03 180 08 140 17 340 24 260 47 300 51 380 83 100 95 220,職工號 姓名 性別 職務 婚否 83 張珊 女 教師 已婚 08 李斯 男 教師 已婚 . 03 王魯 男 教務員 已婚 . 95 劉琪 女 實驗員 未婚 . 24 岳跋 男 教師 已婚 . 47 周斌 男 教師 已婚 . 17 胡江 男 實驗員 未婚 . 51 林青 女 教師 未婚 .,索引表,數(shù)據(jù)表,假設(shè)內(nèi)存工作區(qū)僅能容納 64k 字節(jié)的數(shù)據(jù), 在某一時刻內(nèi)存最多可容納 64 個對象以供搜索。 如果對象總數(shù)有 14400 個, 不可能把所有對象的數(shù)據(jù)一次都讀入內(nèi)存。無論是順序搜索或折半搜索, 都需要多次讀取外存記錄。 如果在索引表中每一個索引項占4個字節(jié), 每個索引項索引一個職工對象, 則 14400 個索引項需要 56.25k 字節(jié), 在內(nèi)存中可以容納所有的索引項。,這樣只需從外存中把索引表讀入內(nèi)存, 經(jīng)過搜索索引后確定了職工對象的存儲地址, 再經(jīng)過 1 次讀取對象操作就可以完成搜索。 稠密索引：一個索引項對應數(shù)據(jù)表中一個對象的索引結(jié)構(gòu)。當對象在外存中按加入順序存放而不是按關(guān)鍵碼有序存放時必須采用稠密索引結(jié)構(gòu)，這時的索引結(jié)構(gòu)叫做索引非順序結(jié)構(gòu)。 稀疏索引：當對象在外存中有序存放時，可以把所有 n 個對象分為 b 個子表(塊)存放，一個索引項對應數(shù)據(jù)表中一組對象(子表)。,在子表中, 所有對象可能按關(guān)鍵碼有序地存放, 也可能無序地存放。但所有這些子表必須分塊有序, 后一個子表中所有對象的關(guān)鍵碼均大于前一個子表中所有對象的關(guān)鍵碼。它們都存放在數(shù)據(jù)區(qū)中。 另外建立一個索引表。索引表中每一表目叫做索引項，它記錄了子表中最大關(guān)鍵碼max _key以及該子表在數(shù)據(jù)區(qū)中的起始位置obj _ addr。 第 i 個索引項是第 i 個子表的索引項, i = 0, 1, , n-1。這樣的索引結(jié)構(gòu)叫做索引順序結(jié)構(gòu)。,對索引順序結(jié)構(gòu)進行搜索時，一般分為兩級搜索: 先在索引表 ID 中搜索給定值 K, 確定滿足 IDi-1.max_key K IDi.max_key,22 12 13 30 29 33,36 42 44 48 39 40,60 74 56 79 80 66,92 82 88 98 94,子表1,子表2,子表3,子表4,數(shù)據(jù)區(qū),33 48 80 98,索引表,1 2 3 4,max_ max_ key addr,的 i 值, 即待查對象可能在的子表的序號。 然后再在第 i 個子表中按給定值搜索要求的對象。 索引表是按max_key有序的, 且長度也不大,可以折半搜索，也可以順序搜索。 各子表內(nèi)各個對象如果也按對象關(guān)鍵碼有序, 可以采用折半搜索或順序搜索; 如果不是按對象關(guān)鍵碼有序, 只能順序搜索。,索引順序搜索的搜索成功時的平均搜索長度 ASLIndexSeq = ASLIndex + ASLSubList 其中, ASLIndex 是在索引表中搜索子表位置的平均搜索長度，ASLSubList 是在子表內(nèi)搜索對象位置的搜索成功的平均搜索長度。 設(shè)把長度為 n 的表分成均等的 b 個子表，每個子表 s 個對象，則 b = n/s。又設(shè)表中每個對象的搜索概率相等，則每個子表的搜索概率為1/b，子表內(nèi)各對象的搜索概率為 1/s。 若對索引表和子表都用順序搜索，則索引順序搜索的搜索成功時的平均搜索長度為 ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1,索引順序搜索的平均搜索長度與表中的對象個數(shù) n 有關(guān)，與每個子表中的對象個數(shù) s 有關(guān)。在給定 n 的情況下，s 應選擇多大？ 用數(shù)學方法可導出, 當 s = 時, ASLIndexSeq取極小值 +1。這個值比順序搜索強，但比折半搜索差。但如果子表存放在外存時，還要受到頁塊大小的制約。 若采用折半搜索確定對象所在的子表, 則搜索成功時的平均搜索長度為 ASLIndexSeq = ASLIndex + ASLSubList log2 (b+1)-1 + (s+1)/2 log2(1+n / s ) + s/2,倒排表 (Inverted Index List),對包含有大量數(shù)據(jù)對象的數(shù)據(jù)表或文件進行搜索時，最常用的是針對對象的主關(guān)鍵碼建立索引。主關(guān)鍵碼可以唯一地標識該對象。用主關(guān)鍵碼建立的索引叫做主索引。 主索引的每個索引項給出對象的關(guān)鍵碼和對象在表或文件中的存放地址。 但在實際應用中有時需要針對其它屬性進行搜索。例如，查詢?nèi)缦碌穆毠ば畔ⅲ?(1) 列出所有教師的名單；,對象關(guān)鍵碼 key 對象存放地址 addr,(2) 已婚的女性職工有哪些人？ 這些信息在數(shù)據(jù)表或文件中都存在，但都不是關(guān)鍵碼，為回答以上問題，只能到表或文件中去順序搜索，搜索效率極低。 因此，除主關(guān)鍵碼外，可以把一些經(jīng)常搜索的屬性設(shè)定為次關(guān)鍵碼，并針對每一個作為次關(guān)鍵碼的屬性，建立次索引。 在次索引中，列出該屬性的所有取值，并對每一個取值建立有序鏈表，把所有具有相同屬性值的對象按存放地址遞增的順序或按主關(guān)鍵碼遞增的順序鏈接在一起。,次索引的索引項由次關(guān)鍵碼、鏈表長度和鏈表本身等三部分組成。 例如，為了回答上述的查詢，我們可以分別建立“性別”、“婚否”和“職務”次索引。,性別次索引,次關(guān)鍵碼 男 女 計 數(shù) 5 3 地址指針,指針 03 08 17 24 47 51 83 95,婚否次索引,次關(guān)鍵碼 已婚 未婚 計 數(shù) 5 3 地址指針,指針 03 08 24 47 83 17 51 95,職務次索引,次關(guān)鍵碼 教師 教務員 實驗員 計 數(shù) 5 1 2 地址指針,指針 08 24 47 51 83 03 17 95,(1) 列出所有教師的名單； (2) 已婚的女性職工有哪些人？ 通過順序訪問“職務”次索引中的“教師”鏈，可以回答上面的查詢(1)。 通過對“性別”和“婚否”次索引中的“女性”鏈和“已婚”鏈進行求“交”運算，就能夠找到所有既是女性又已婚的職工對象，從而回答上面的查詢(2)。 倒排表是次索引的一種實現(xiàn)。在表中所有次關(guān)鍵碼的鏈都保存在次索引中，僅通過搜索次索引就能找到所有具有相同屬性值的對象。,在次索引中記錄對象存放位置的指針可以用主關(guān)鍵碼表示: 可通過搜索次索引確定該對象的主關(guān)鍵碼, 再通過搜索主索引確定對象的存放地址。 在倒排表中各個屬性鏈表的長度大小不一,管理比較困難。為此引入單元式倒排表。 在單元式倒排表中, 索引項中不存放對象的存儲地址, 存放該對象所在硬件區(qū)域的標識。 硬件區(qū)域可以是磁盤柱面、磁道或一個頁塊, 以一次 I / O 操作能存取的存儲空間作為硬件區(qū)域為最好。,為使索引空間最小, 在索引中標識這個硬件區(qū)域時可以使用一個能轉(zhuǎn)換成地址的二進制數(shù),整個次索引形成一個(二進制數(shù)的) 位矩陣。 例如, 對于記錄學生信息的文件, 次索引可以是如圖所示的結(jié)構(gòu)。二進位的值為 1 的硬件區(qū)域包含具有該次關(guān)鍵碼的對象。 如果在硬件區(qū)域1，中有要求的對象。然后將硬件區(qū)域1，等讀入內(nèi)存，在其中進行檢索，確定就可取出所需對象。,單元式倒排表結(jié)構(gòu),m 路靜態(tài)搜索樹,當數(shù)據(jù)對象數(shù)目特別大，索引表本身也很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表搜索一遍。 此時, 可以建立索引的索引(二級索引)。二級索引可以常駐內(nèi)存，二級索引中一個索引項對應一個索引塊，登記該索引塊的最大關(guān)鍵碼及該索引塊的存儲地址。,如果二級索引在內(nèi)存中也放不下，需要分為許多塊多次從外存讀入?？梢越⒍壦饕乃饕?三級索引)。這時，訪問外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對象。,02 06,11 15,18 23,29 32,38 41,45 49,52 60,77 95,(06, ) (15, ) (23, ),(06, ) (15, ) (23, ),(32, ) (41, ) (49, ),(60, ) (95, ),(23, ) (41, ) (95, ),root,head,必要時, 還可以有4級索引, 5極索引, 。 這種多級索引結(jié)構(gòu)形成一種 m 叉樹。樹中每一個分支結(jié)點表示一個索引塊, 它最多存放 m 個索引項, 每個索引項分別給出各子樹結(jié)點 (低一級索引塊) 的最大關(guān)鍵碼和結(jié)點地址。 樹的葉結(jié)點中各索引項給出在數(shù)據(jù)表中存放的對象的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級索引，就是m路搜索樹。 m路搜索樹可能是靜態(tài)索引結(jié)構(gòu)，即結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時就已經(jīng)定型，在整個運行期間，樹的結(jié)構(gòu)不發(fā)生變化。,多級索引結(jié)構(gòu)形成 m 路搜索樹,m路搜索樹還可能是動態(tài)索引結(jié)構(gòu), 即在整個系統(tǒng)運行期間, 樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時調(diào)整, 以保持最佳的搜索效率。,數(shù)據(jù)區(qū),一級索引,二級索引,三級索引,四級索引,動態(tài)搜索結(jié)構(gòu),現(xiàn)在我們所討論的 m 路搜索樹多為可以動態(tài)調(diào)整的多路搜索樹，它的一般定義為： 一棵 m 路搜索樹, 它或者是一棵空樹, 或者是滿足如下性質(zhì)的樹： 根最多有 m 棵子樹, 并具有如下的結(jié)構(gòu)： n, P0, ( K1, P1 ), ( K2, P2 ), , ( Kn, Pn ) 其中, Pi 是指向子樹的指針, 0 i n m; Ki 是關(guān)鍵碼, 1 i n m。 Ki Ki+1, 1 i n。,動態(tài)的 m 路搜索樹,在子樹 Pi 中所有的關(guān)鍵碼都小于 Ki+1, 且大于 Ki，0 i n。 在子樹 Pn 中所有的關(guān)鍵碼都大于Kn； 在子樹 P0 中的所有關(guān)鍵碼都小于 K1。 子樹 Pi 也是 m 路搜索樹，0 i n。,一棵3路搜索樹的示例,35,20 40,a,b,c,d,e,25 30,10 15,45 50,m 路搜索樹的類定義 template class Mtree /基類 public: Triple ,AVL樹是2路搜索樹。如果已知 m 路搜索樹的度 m 和它的高度 h, 則樹中的最大結(jié)點數(shù)為,(等比級數(shù)前 h 項求和),每個結(jié)點中最多有 m-1 個關(guān)鍵碼，在一棵高度為 h 的 m 路搜索樹中關(guān)鍵碼的最大個數(shù)為 mh+1-1。 高度 h=2 的二叉樹, 關(guān)鍵碼最大個數(shù)為7； 高度 h=3 的3路搜索樹, 關(guān)鍵碼最大個數(shù)為 34-1 = 80。,struct Triple Mnode * r; /結(jié)點地址指針 int i; int tag; /結(jié)點中關(guān)鍵碼序號 i ; /tag=0,搜索成功；tag=1,搜索不成功,標識 m 路搜索樹搜索結(jié)果的三元組表示,m 路搜索樹上的搜索算法,在 m 路搜索樹上的搜索過程是一個在結(jié)點內(nèi)搜索和自根結(jié)點向下逐個結(jié)點搜索的交替的過程。,35,20 40,a,b,c,d,e,25 30,10 15,45 50,root,搜索35,template Triple ,q = p; p = p-ptri; /向下一層結(jié)點搜索 GetNode (p); /讀入該結(jié)點 result.r = q; result.i = i; result.tag = 1; return result; /搜索失敗,返回插入位置 ,提高搜索樹的路數(shù) m, 可以改善樹的搜索性能。對于給定的關(guān)鍵碼數(shù) n，如果搜索樹是平衡的，可以使 m 路搜索樹的性能接近最佳。下面將討論一種稱之為B 樹的平衡的 m 路搜索樹。,B 樹,一棵 m 階B 樹是一棵平衡的 m 路搜索樹, 它或者是空樹, 或者是滿足下列性質(zhì)的樹： 根結(jié)點至少有 2 個子女。 除根結(jié)點以外的所有結(jié)點 (不包括失敗結(jié)點)至少有 m/2 個子女。 所有的失敗結(jié)點都位于同一層。 在B 樹中的“失敗”結(jié)點是當搜索值x不在樹中時才能到達的結(jié)點。 事實上，在B 樹的每個結(jié)點中還包含有一組指針Dm，指向?qū)嶋H對象的存放地址。,30,Ki與Di (1 i n m) 形成一個索引項(Ki, Di)，通過Ki可找到某個對象的存儲地址Di。 一棵B 樹是平衡的 m 路搜索樹，但一棵平衡的 m 路搜索樹不一定是B 樹。,35,20 40,25 30,10 15,45 50,root,45 50,35,40,20,root,10 15,25,非B 樹 B 樹,B 樹的類定義和B 樹結(jié)點類定義 template class Btree : public Mtree /繼承 m 路搜索樹的所有屬性和操作 public: int Insert ( const Type template class Mnode / B 樹結(jié)點類定義 private:,int n; /結(jié)點中關(guān)鍵碼個數(shù) Mnode *parent; /雙親指針 Type keym+1; /關(guān)鍵碼數(shù)組 1m-1 Mnode *ptrm+1; /子樹指針數(shù)組 ;,B 樹的搜索算法,B 樹的搜索算法繼承了 m 路搜索樹Mtree上的搜索算法。 B 樹的搜索過程是一個在結(jié)點內(nèi)搜索和循某一條路徑向下一層搜索交替進行的過程。,B 樹的搜索時間與B 樹的階數(shù) m 和B 樹的高度h直接有關(guān), 必須加以權(quán)衡。 在B 樹上進行搜索, 搜索成功所需的時間取決于關(guān)鍵碼所在的層次; 搜索不成功所需的時間取決于樹的高度。 如果定義B 樹的高度h 為失敗結(jié)點所在的層次，需要了解樹的高度h 與樹中的關(guān)鍵碼個數(shù) N 之間的關(guān)系。 如果讓B 樹每層結(jié)點個數(shù)達到最大，且設(shè)關(guān)鍵碼總數(shù)為N, 則樹的高度達到最?。?h = logm( N*(m-2)/(m-1)+1) -1,設(shè)在 m 階B 樹中每層結(jié)點個數(shù)達到最少, 則B 樹的高度可能達到最大。設(shè)樹中關(guān)鍵碼個數(shù)為 N，從B 樹的定義知： 0層 1 個結(jié)點 1層 至少 2 個結(jié)點 2層 至少 2 m / 2 個結(jié)點 3層 至少 2 m / 2 2 個結(jié)點 如此類推， h-1 層 至少有 2 m / 2 h-2 個結(jié)點。所有這些結(jié)點都不是失敗結(jié)點。,高度h與關(guān)鍵碼個數(shù)N之間的關(guān)系,若樹中關(guān)鍵碼有N個, 則失敗結(jié)點數(shù)為N+1。這是因為失敗數(shù)據(jù)一般與已有關(guān)鍵碼交錯排列。因此，有 N +1 = 失敗結(jié)點數(shù) = 位于第 h 層的結(jié)點數(shù) 2 m / 2 h-1 N 2 m / 2 h-1-1 h-1 log m / 2 ( (N +1) / 2 ) 所有的非失敗結(jié)點所在層次為0 h-1。 示例：若B 樹的階數(shù) m = 199, 關(guān)鍵碼總數(shù) N = 1999999，則B 樹的高度 h 不超過 log100 1000000 +1= 4,m值的選擇,如果提高B 樹的階數(shù) m, 可以減少樹的高度, 從而減少讀入結(jié)點的次數(shù), 因而可減少讀磁盤的次數(shù)。 事實上，m 受到內(nèi)存可使用空間的限制。當 m 很大超出內(nèi)存工作區(qū)容量時, 結(jié)點不能一次讀入到內(nèi)存, 增加了讀盤次數(shù), 也增加了結(jié)點內(nèi)搜索的難度。 m值的選擇 : 應使得在B 樹中找到關(guān)鍵碼 x 的時間總量達到最小。 這個時間由兩部分組成：,從磁盤中讀入結(jié)點所用時間 在結(jié)點中搜索 x 所用時間 根據(jù)定義, B 樹的每個結(jié)點的大小都是固定的, 結(jié)點內(nèi)有 m-1 個索引項 (Ki, Di, Pi), 1 i m。其中，Ki 所占字節(jié)數(shù)為，Di 和 Pi 所占字節(jié)數(shù)為，則結(jié)點大小近似為 m(+2) 個字節(jié)。讀入一個結(jié)點所用時間為： tseek + tlatency + m( + 2) ttran = a + bm,B 樹的插入,B 樹是從空樹起, 逐個插入關(guān)鍵碼而生成的。 在B 樹，每個非失敗結(jié)點的關(guān)鍵碼個數(shù)都在 m/2 -1, m-1 之間。 插入在某個葉結(jié)點開始。如果在關(guān)鍵碼插入后結(jié)點中的關(guān)鍵碼個數(shù)超出了上界 m-1，則結(jié)點需要“分裂”，否則可以直接插入。 實現(xiàn)結(jié)點“分裂”的原則是： 設(shè)結(jié)點 p 中已經(jīng)有 m-1 個關(guān)鍵碼，當再插入一個關(guān)鍵碼后結(jié)點中的狀態(tài)為,( m, P0, K1, P1, K2, P2, , Km, Pm) 其中 Ki Ki+1, 1 i m 這時必須把結(jié)點 p 分裂成兩個結(jié)點 p 和 q，它們包含的信息分別為： 結(jié)點 p： ( m/2 -1, P0, K1, P1, , Km/2 -1, Pm/2 -1) 結(jié)點 q： (m-m/2, Pm/2, Km/2+1, Pm/2+1, , Km, Pm) 位于中間的關(guān)鍵碼 Km/2 與指向新結(jié)點 q 的指針形成一個二元組 ( Km/2, q )，插入到這兩個結(jié)點的雙親結(jié)點中去。,結(jié)點“分裂”的示例,2 53 75,n P0 K1 P1 K2 P2,p,3 53 75 139,n P0 K1 P1 K2 P2 K3 P3,p,加入139, 結(jié)點溢出,1 75,n P0 K1 P1,1 53,n P0 K1 P1,1 139,n P0 K1 P1,結(jié)點 分裂,P,q,49 75,示例:從空樹開始加入關(guān)鍵碼建立3階B 樹,n=1 加入53,53,n=2 加入75,53 75,n=3 加入139,75,139,53,n=5 加入49,145,75,139 145,49 53,n=6 加入36,139 145,53,36,在插入新關(guān)鍵碼時，需要自底向上分裂結(jié)點，最壞情況下從被插關(guān)鍵碼所在葉結(jié)點到根的路徑上的所有結(jié)點都要分裂。,若設(shè)B 樹的 高度為h, 那么在自頂向下搜索到葉結(jié)點的過程中需要進行 h 次讀盤。,n=7 加入101,49,53,36,139,145,101,75,B 樹的插入算法 template int Btree : Insert ( const Type /寫出, /結(jié)點已滿,分裂 int s = (m+1)/2; /求 m/2 insertkey ( p, j, K, ap ); /(K,ap)插入 j后 q = new Mnode; /建立新結(jié)點 move ( p, q, s, m ); /從 p向q 搬送 K = p-keys; ap = q; /分界碼上移 if ( p-parent != NULL ) /雙親不是根 t = p-parent; GetNode (t); /讀入雙親 j = 0; t-key(t-n)+1 = MAXKEY; while ( t-keyj+1 parent = p-parent; PutNode (p); PutNode (q);,p = t; /繼續(xù) while(1) 循環(huán),向上調(diào)整 else /雙親是根 root = new Mnode; /創(chuàng)建新根 root-n = 1; root-parent = NULL; root-key1 = K; root-ptr0 = p; root-ptr1 = ap; q-parent = p-parent = root; PutNode (p); PutNode (q); PutNode (root); return 1; /跳出返回 ,當分裂一個非根的結(jié)點時需要向磁盤寫出 2 個結(jié)點, 當分裂根結(jié)點時需要寫出 3 個結(jié)點。 如果我們所用的內(nèi)存工作區(qū)足夠大, 使得在向下搜索時, 讀入的結(jié)點在插入后向上分裂時不必再從磁盤讀入, 那么, 在完成一次插入操作時需要讀寫磁盤的次數(shù) = = 找插入結(jié)點向下讀盤次數(shù) + + 分裂非根結(jié)點時寫盤次數(shù) + + 分裂根結(jié)點時寫盤次數(shù) = = h+2(h-1)+3 = = 3h+1。,B 樹的刪除,在B 樹上刪除一個關(guān)鍵碼時, 首先需要找到這個關(guān)鍵碼所在的結(jié)點, 從中刪去這個關(guān)鍵碼。若該結(jié)點不是葉結(jié)點, 且被刪關(guān)鍵碼為 Ki, 1 i n, 則在刪去該關(guān)鍵碼之后, 應以該結(jié)點 Pi 所指示子樹中的最小關(guān)鍵碼 x 來代替被刪關(guān)鍵碼 Ki 所在的位置, 然后在 x 所在的葉結(jié)點中刪除 x。 在葉結(jié)點上的刪除有 4 種情況。 被刪關(guān)鍵碼所在葉結(jié)點同時又是根結(jié)點且刪除前該結(jié)點中關(guān)鍵碼個數(shù) n 2，則直接刪去該關(guān)鍵碼并將修改后的結(jié)點寫回磁盤。,被刪關(guān)鍵碼所在葉結(jié)點不是根結(jié)點且刪除前該結(jié)點中關(guān)鍵碼個數(shù) n m/2 , 則直接刪去該關(guān)鍵碼并將修改后的結(jié)點寫回磁盤, 刪除結(jié)束。 被刪關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼個數(shù) n = m/2 -1, 若這時與該結(jié)點相鄰的右兄弟 (或左兄弟) 結(jié)點的關(guān)鍵碼個數(shù) n m/2，則可按以下步驟調(diào)整該結(jié)點、右兄弟 (或左兄弟) 結(jié)點以及其雙親結(jié)點，以達到新的平衡。,36 49,m = 3,刪除36,49,55 58,刪除55,簡單刪除,75 80,m = 3,刪除55,10,40,65,60 70,30,50,a,c,b,d,e,f,g,h,58,75 80,10,40,65,60 70,30,50,a,c,b,d,e,f,g,h,將雙親結(jié)點中剛剛大于 (或小于) 該被刪關(guān)鍵碼的關(guān)鍵碼 Ki (1 i n) 下移； 將右兄弟 (或左兄弟) 結(jié)點中的最小 (或最大)關(guān)鍵碼上移到雙親結(jié)點的 Ki 位置； 將右兄弟 (或左兄弟) 結(jié)點中的最左 (或最右) 子樹指針平移到被刪關(guān)鍵碼所在結(jié)點中最后 (或最前) 子樹指針位置； 在右兄弟 (或左兄弟) 結(jié)點中，將被移走的關(guān)鍵碼和指針位置用剩余的關(guān)鍵碼和指針填補、調(diào)整。再將結(jié)點中的關(guān)鍵碼個數(shù)減1。,結(jié)點聯(lián)合調(diào)整,55 58,75 80,m = 3,刪除65,10,40,65,60 70,30,50,a,c,b,d,e,f,g,h,55 58,80,10,40,70,60 75,30,50,a,c,b,d,e,f,g,h,調(diào)整g,c,h,刪除65,70,刪除70,55 58,80,m = 3,刪除70,10,40,60 75,30,50,a,c,b,d,e,f,g,h,55,80,10,40,60,58 75,30,50,a,c,b,d,e,f,g,h,調(diào)整f,c,g,結(jié)點聯(lián)合調(diào)整,被刪關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼個數(shù) n = m/2 -1, 若這時與該結(jié)點相鄰的右兄弟 (或左兄弟) 結(jié)點的關(guān)鍵碼個數(shù) n = m/2 -1, 則必須按以下步驟合并這兩個結(jié)點。 將雙親結(jié)點 p 中相應關(guān)鍵碼下移到選定保留的結(jié)點中。若要合并 p 中的子樹指針 Pi 與 Pi+1 所指的結(jié)點, 且保留 Pi 所指結(jié)點,則把 p 中的關(guān)鍵碼 Ki+1下移到 Pi 所指的結(jié)點中。 把 p 中子樹指針 Pi+1 所指結(jié)點中的全部指針和關(guān)鍵碼都照搬到 Pi 所指結(jié)點的后面。刪去 Pi+1 所指的結(jié)點。,在結(jié)點 p 中用后面剩余的關(guān)鍵碼和指針填補關(guān)鍵碼 Ki+1 和指針 Pi+1。 修改結(jié)點 p 和選定保留結(jié)點的關(guān)鍵碼個數(shù)。 在合并結(jié)點的過程中, 雙親結(jié)點中的關(guān)鍵碼個數(shù)減少了。 若雙親結(jié)點是根結(jié)點且結(jié)點關(guān)鍵碼個數(shù)減到 0, 則將該雙親結(jié)點刪去, 合并后保留的結(jié)點成為新的根結(jié)點; 否則將雙親結(jié)點與合并后保留的結(jié)點都寫回磁盤, 刪除處理結(jié)束。 若雙親結(jié)點不是根結(jié)點且關(guān)鍵碼個數(shù)減到m/2 -2，又要與它自己的兄弟結(jié)點合并, 重復上面的合并步驟。最壞情況下這種結(jié)點合并處理要自下向上直到根結(jié)點。,55,刪除55,結(jié)點合并,80,m = 3,刪除55,10,40,60,58 75,30,50,a,c,b,d,e,f,g,h,合并f, g,58 60,80,10,40,75,30,50,a,c,b,d,e,f,h,80,55,刪除80,結(jié)點合并,m = 3,刪除80,10,40,60,58 75,30,50,a,c,b,d,e,f,g,h,合并g, h,60 75,55,10,40,58,30,50,a,c,b,d,e,f,h,55,非葉結(jié)點刪除,刪除50,刪除55,55 58,75 80,m = 3,刪除50,10,40,65,60 70,30,50,a,c,b,d,e,f,g,h,58,75 80,刪除55,10,40,65,60 70,30,a,c,b,d,e,f,g,h,用55取代,用58取代,58,75 80,10,40,65,60 70,30,a,c,b,d,e,f,g,h,合并f, g,58,75 80,10,40,60 65,70,30,a,c,b,d,e,f,h,結(jié)點合并與調(diào)整,刪除70,58,80,10,40,60 65,75,30,a,c,b,d,e,f,h,刪除70,用75取代,刪除75,58,10,40,60 65,80,30,a,c,b,d,e,f,h,刪除75,用80取代 調(diào)整f, c, h,58,80,10,40,60,65,30,a,c,b,d,e,f,h,刪除10,80,30 40,60,f,h,58 65,d,b,B 樹的關(guān)鍵碼刪除算法 template int Btree : Delete ( const Type /在葉結(jié)點刪除,p = q; /轉(zhuǎn)化為葉結(jié)點的刪除 else compress ( p, j ); /葉結(jié)點,直接刪除 int d = (m+1)/2; /求 m/2 while (1) /調(diào)整或合并 if ( p-n parent; /找到雙親 GetNode (q); while ( j n ,p = q; /向上調(diào)整 if ( p = root ) break; else break; if ( !root-n ) /調(diào)整后根的n減到0 p = root-ptr0; delete root; root = p; /刪根 root-parent = NULL; /新根 ,B+樹,一棵 m 階B+樹可以定義如下： 樹中每個非葉結(jié)點最多有 m 棵子樹； 根結(jié)點(非葉結(jié)點)至少有 2 棵子樹。除根結(jié)點外, 其它的非葉結(jié)點至少有 m/2 棵子樹; 有 n 棵子樹的非葉結(jié)點有 n-1 個關(guān)鍵碼。 所有葉結(jié)點都處于同一層次上, 包含了全部關(guān)鍵碼及指向相應數(shù)據(jù)對象存放地址的指針, 且葉結(jié)點本身按關(guān)鍵碼從小到大順序鏈接；,葉結(jié)點的子樹棵數(shù) n 可以多于 m, 可以少于 m, 視關(guān)鍵碼字節(jié)數(shù)及對象地址指針字節(jié)數(shù)而定。若設(shè)結(jié)點可容納最大關(guān)鍵碼數(shù)為 m1, 則指向?qū)ο蟮牡刂分羔樢灿?m1 個。,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,葉結(jié)點中的子樹棵數(shù) n 應滿足 n m1/2 , m1。 若根結(jié)點同時又是葉結(jié)點, 則結(jié)點格式同葉結(jié)點。 所有的非葉結(jié)點可以看成是索引部分, 結(jié)點中關(guān)鍵碼 Ki 與指向子樹的指針 Pi 構(gòu)成對子樹(即下一層索引塊)的索引項( Ki, Pi )，Ki 是子樹中最小的關(guān)鍵碼。 特別地, 子樹指針 P0 所指子樹上所有關(guān)鍵碼均小于 K1。結(jié)點格式同B 樹。,葉結(jié)點中存放的是對實際數(shù)據(jù)對象的索引。,在B+樹中有兩個頭指針: 一個指向 B+ 樹的根結(jié)點，一個指向關(guān)鍵碼最小的葉結(jié)點。 可對B+樹進行兩種搜索運算： 循葉結(jié)點鏈順序搜索 另一種是從根結(jié)點開始, 進行自頂向下, 直至葉結(jié)點的隨機搜索。 在B+樹上進行隨機搜索、插入和刪除的過程基本上與B 樹類似。只是在搜索過程中，如果非葉結(jié)點上的關(guān)鍵碼等于給定值，搜索并不停止，而是繼續(xù)沿右指針向下，一直查到葉結(jié)點上的這個關(guān)鍵碼。,B+樹的搜索分析類似于B 樹。 B+樹的插入僅在葉結(jié)點上進行。 每插入一 個(關(guān)鍵碼-指針)索引項后都要判斷結(jié)點中的子樹棵數(shù)是否超出范圍。 當插入后結(jié)點中的子樹棵數(shù) n m1 時, 需要將葉結(jié)點分裂為兩個結(jié)點, 它們的關(guān)鍵碼分別為 (m1+1)/2 和 (m1+1)/2。 它們的雙親結(jié)點中應同時包含這兩個結(jié)點的最小關(guān)鍵碼和結(jié)點地址。此后, 問題歸于在非葉結(jié)點中的插入了。,3個關(guān)鍵碼的B+樹,10 12 23,加入關(guān)鍵碼33,結(jié)點分裂,10 12,23 33,23,10 12,18 20 22,23 33,18 23,加入更多的關(guān)鍵碼,在非葉結(jié)點中關(guān)鍵碼的插入與葉結(jié)點的插入類似, 但非葉結(jié)點中的子樹棵數(shù)的上限為 m, 超出這個范圍就需要進行結(jié)點分裂。 在做根結(jié)點分裂時, 因為沒有雙親結(jié)點, 就必須創(chuàng)建新的雙親結(jié)點, 作為樹的新根。這樣樹的高度就增加一層了。 B+樹的刪除僅在葉結(jié)點上進行。當在葉結(jié)點上刪除一個(關(guān)鍵碼-指針)索引項后, 結(jié)點中的子樹棵數(shù)仍然不少于 m1/2，這屬于簡單刪除, 其上層索引可以不改變。,如果刪除的關(guān)鍵碼是該結(jié)點的最小關(guān)鍵碼, 但因在其上層的副本只是起了一個引導搜索的“分界關(guān)鍵碼”的作用, 所以上層的副本仍然可以保留。 如果在葉結(jié)點中刪除一個(關(guān)鍵碼-指針)索引項后，該結(jié)點中的子樹棵數(shù) n 小于結(jié)點子樹棵數(shù)的下限 m1/2，必須做結(jié)點的調(diào)整或合并工作。,刪除18,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,10 15,20 22,23 31,33 45,48 52,18 23,33,33,刪除關(guān)鍵碼18 上層索引不改,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,15 18,20 22,23 31,33 45,48 52,20 23,33,33,刪除關(guān)鍵碼10, 18移入結(jié)點,索 引改20,刪除10,如果右兄弟結(jié)點的子樹棵數(shù)已達到下限m1/2，沒有多余的關(guān)鍵碼可以移入被刪關(guān)鍵碼所在的結(jié)點, 必須進行兩個結(jié)點的合并。將右兄弟結(jié)點中的所有(關(guān)鍵碼-指針)索引項移入被刪關(guān)鍵碼所在結(jié)點，再將右兄弟結(jié)點刪去。 結(jié)點的合并將導致雙親結(jié)點中“分界關(guān)鍵碼”的減少, 有可能減到非葉結(jié)點中子樹棵數(shù)的下限 m/2 以下。這樣將引起非葉結(jié)點的調(diào)整或合并。如果根結(jié)點的最后兩個子女結(jié)點合并，樹的層數(shù)就會減少一層。,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,15 18,20 22,23 31,20 23 45,刪除關(guān)鍵碼33, 右邊兩結(jié)點合并, 影響到非葉結(jié)點合并,可能直到根結(jié)點,導致高度減少,刪除33,45 48 52,散列 (Hashing),在計算科學中把詞典當作一種抽象數(shù)據(jù)類型。 在討論詞典抽象數(shù)據(jù)類型時，把詞典定義為 對的集合。,在現(xiàn)實中, 經(jīng)常遇到按給定的值進行查詢的事例。為此, 必須在開發(fā)相應軟件時考慮在記錄的存放位置和用以標識它的數(shù)據(jù)項 (稱為關(guān)鍵碼)之間的對應關(guān)系,從而選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu), 很方便地根據(jù)記錄的關(guān)鍵碼檢索到對應記錄的信息。,詞典(Dictionary)的抽象數(shù)據(jù)類型,根據(jù)問題的不同, 可以為名字和屬性賦予不同的含義。 例如, 在圖書館檢索目錄中, 名字是書名, 屬性是索書號及作者等信息; 在計算機活動文件表中, 名字是文件名, 屬性是文件地址、大小等信息。,詞典的抽象數(shù)據(jù)類型 const int DefaultSize = 26; template class Dictionary public:,Dictionary ( int size = DefaultSize ); int IsIn ( Name name ); Attribute * Find ( Name name ); void Insert ( Name name, Attribute attr ); void Remove ( Name name ); ,在詞典的所有操作中，最基本的只有 3 種：Find (搜索)、Insert (插入)、Remove (刪除)。 在選擇詞典的表示時，必須確保這幾個操作的實現(xiàn)。,通常，用文件 (表格) 來表示實際的對象集合, 用文件記錄 (表格的表項) 來表示單個對象。這樣, 詞典中的對將被存于記錄 (表項) 中，通過表項的關(guān)鍵碼 ( 對的名字) 來標識該表項。 表項的存放位置及其關(guān)鍵碼之間的對應關(guān)系可以用一個二元組表示： ( 關(guān)鍵碼key，表項位置指針addr ) 這個二元組構(gòu)成搜索某一指定表項的索引項。 考慮到搜索效率, 可以用順序表方式、二叉搜索樹或多路搜索樹方式組織詞典。本節(jié)討論另一種組織詞典的方法, 即散列表結(jié)構(gòu)。,靜態(tài)散列方法,散列方法在表項存儲位置與其關(guān)鍵碼之間建立一個確定的對應函數(shù)關(guān)系Hash( )，使每個關(guān)鍵碼與結(jié)構(gòu)中一個唯一存儲位置相對應： Address Hash ( Rec.key ) 在搜索時, 先對表項的關(guān)鍵碼進行函數(shù)計算,把函數(shù)值當做表項的存儲位置, 在結(jié)構(gòu)中按此位置取表項比較。若關(guān)鍵碼相等, 則搜索成功。在存放表項時, 依相同函數(shù)計算存儲位置, 并按此位置存放。這種方法就是散列方法。,在散列方法中使用的轉(zhuǎn)換函數(shù)叫做散列函數(shù)。按此方法構(gòu)造出來的表或結(jié)構(gòu)就叫做散列表。 使用散列方法進行搜索不必進行多次關(guān)鍵碼的比較, 搜索速度比較快, 可以直接到達或逼近具有此關(guān)鍵碼的表項的實際存放地址。 散列函數(shù)是一個壓縮映象函數(shù)。關(guān)鍵碼集合比散列表地址集合大得多。因此有可能經(jīng)過散列函數(shù)的計算，把不同的關(guān)鍵碼映射到同一個散列地址上，這就產(chǎn)生了沖突。 示例：有一組表項，其關(guān)鍵碼分別是 12361, 07251, 03309, 30976,采用的散列函數(shù)是 hash(x) = x % 73 + 13420 其中，“%”是除法取余操作。 則有：hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。就是說, 對不同的關(guān)鍵碼, 通過散列函數(shù)的計算, 得到了同一散列地址。我們稱這些產(chǎn)生沖突的散列地址相同的不同關(guān)鍵碼為同義詞。 由于關(guān)鍵碼集合比地址集合大得多, 沖突很難避免。所以對于散列方法, 需要討論以下兩個問題：,構(gòu)造散列函數(shù)時的幾點要求： 散列函數(shù)應是簡單的，能在較短的時間內(nèi)計 算出結(jié)果。 散列函數(shù)的定義域必須包括需要存儲的全部 關(guān)鍵碼, 如果散列表允許有 m 個地址時, 其 值域必須在 0 到 m-1 之間。,散列函數(shù),對于給定的一個關(guān)鍵碼集合, 選擇一個計算簡單且地址分布比較均勻的散列函數(shù), 避免或盡量減少沖突； 擬訂解決沖突的方案。,直接定址法 此類函數(shù)取關(guān)鍵碼的某個線性函數(shù)值作為散列地址： Hash ( key ) a * key + b a, b為常數(shù) 這類散列函數(shù)是一對一的映射，一般不會產(chǎn)生沖突。但是，它要求散列地址空間的大小與關(guān)鍵碼集合的大小相同。,散列函數(shù)計算出來的地址應能均勻分布在整 個地址空間中 : 若 key 是從關(guān)鍵碼集合中隨 機抽取的一個關(guān)鍵碼, 散列函數(shù)應能以同等 概率取0 到 m-1 中的每一個值。,示例：有一組關(guān)鍵碼如下： 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 。散列函數(shù)為 Hash (key) = key - 940000 Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527 Hash (941630) = 1630 Hash (941805) = 1805 Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按計算出的地址存放記錄。 數(shù)字分析法,設(shè)有 n 個 d 位數(shù), 每一位可能有 r 種不同的符號。這 r 種不同的符號在各位上出現(xiàn)的頻率不一定相同。 可根據(jù)散列表的大小, 選取其中各種符號分布均勻的若干位作為散列地址。 計算各位數(shù)字中符號分布均勻度 k 的公式： 其中， 表示第 i 個符號在第 k 位上出現(xiàn)的次數(shù)，n/r 表示各種符號在 n 個數(shù)中均勻出現(xiàn)的期望值。計算出的 k 值越小，表明在該位 (第 k 位) 各種符號分布得越均勻。,9 4 2 1 4 8 位， 1 = 57.60 9 4 1 2 6 9 位， 2 = 57.60 9 4 0 5 2 7 位， 3 = 17.60 9 4 1 6 3 0 位， 4 = 5.60 9 4 1 8 0 5 位， 5 = 5.60 9 4 1 5 5 8 位， 6 = 5.60 9 4 2 0 4 7 9 4 0 0 0 1 ,若散列表地址范圍有 3 位數(shù)字, 取各關(guān)鍵碼的 位做為記錄的散列地址。也可以把第，, 和第位相加, 舍去進位位, 變成一位數(shù), 與第, 位合起來作為散列地址。,數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況，它完全依賴于關(guān)鍵碼集合。如果換一個關(guān)鍵碼集合，選擇哪幾位要重新決定。 除留余數(shù)法 設(shè)散列表中允許地址數(shù)為 m, 取一個不大于 m, 但最接近于或等于 m 的質(zhì)數(shù) p 作為除數(shù), 利用以下函數(shù)把關(guān)鍵碼轉(zhuǎn)換成散列地址： hash ( key ) = key % p p m 其中, “%”是整數(shù)除法取余的運算，要求這時的質(zhì)數(shù) p 不是接近2的冪。,示例: 有一個關(guān)鍵碼 key = 962148, 散列表大小 m = 25, 即 HT25。取質(zhì)數(shù) p= 23。散列函數(shù) hash ( key ) = key % p。則散列地址為 hash ( 962148 ) = 962148 % 23 = 12。 可以按計算出的地址存放記錄。需要注意的是, 使用上面的散列函數(shù)計算出來的地址范圍是 0到 22, 因此, 從23到24這幾個散列地址實際上在一開始是不可能用散列函數(shù)計算出來的, 只可能在處理溢出時達到這些地址。 平方取中法 此方法在詞典處理中使用十分廣泛。,它先計算構(gòu)成關(guān)鍵碼的標識符的內(nèi)碼的平方, 然后按照散列表的大小取中間的若干位作為散列地址。 設(shè)標識符可以用一個計算機字長的內(nèi)碼表示。因為內(nèi)碼平方數(shù)的中間幾位一般是由標識符所有字符決定, 所以對不同的標識符計算出的散列地址大多不相同, 即使其中有些字符相同。 在平方取中法中, 一般取散列地址為 2 的某次冪。例如, 若散列地址總數(shù)取為 m = 2r，則對內(nèi)碼的平方數(shù)取中間的 r 位。如果 r = 3，所取得的散列地址參看圖的最右一列。,標識符 內(nèi)碼 內(nèi)碼的平方 散列地址 A 01 01 001 A1 0134 20420 042 A9 0144 23420 342 B 02 4 004 DMAX 04150130 21526443617100 443 DMAX1 0415013034 5264473522151420 352 AMAX 01150130 135423617100 236 AMAX1 0115013034 3454246522151420 652,標識符的八進制內(nèi)碼表示及其平方值,折疊法 此方法把關(guān)鍵碼自左到右分成位數(shù)相等的幾部分, 每一部分的位數(shù)應與散列表地址位數(shù)相同, 只有最后一部分的位數(shù)可以短一些。 把這些部分的數(shù)據(jù)疊加起來, 就可以得到具有該關(guān)鍵碼的記錄的散列地址。 有兩種疊加方法： 移位法 把各部分的最后一位對齊相加； 分界法 各部分不折斷, 沿各部分的分界來回折疊, 然后對齊相加, 將相加的結(jié)果當做散列地址。,示例: 設(shè)給定的關(guān)鍵碼為 key = 23938587841, 若存儲空間限定 3 位, 則劃分結(jié)果為