課件-10補充12.2廣義表和存儲管理

11補充考研內(nèi)11.4.1B11.4.2B+ 數(shù)12.2廣義表 管補充考研內(nèi) 基本概11.1線性索11.2靜態(tài)索11.3倒排索11.4動態(tài)索B/B+11.5位索引技 樹——以前補充考研內(nèi) 索引(indexing)——(關(guān)鍵碼，指–指針指向“主文件”中的完整記索引文件indexfile索引技術(shù)是組織大型數(shù)據(jù)庫的一種重要–高效率的檢 、更新、刪(20,a9) (50,a5)補充考研內(nèi) 按照關(guān)鍵碼的順序進(jìn)行排 線性索引文數(shù)據(jù)庫補充考研內(nèi) 動態(tài)索引結(jié)索引結(jié)構(gòu)本身也可能發(fā)生改在系統(tǒng)運行過程 或刪除記錄目保持較好的性例如較高的檢索補充考研內(nèi) 一種平衡的多(Balanced18183階B23204550補充考研內(nèi) B 補充考研內(nèi) 關(guān)鍵 文件頁內(nèi)地(18,a1)))

(23,a4)

(20,a9)

主文補充考研內(nèi) (1)每個結(jié)點至多有m個子結(jié)點(2)除根結(jié)點和葉結(jié)點外，其它每個結(jié)點至少

子結(jié)點(3)根結(jié)點至少有兩個子唯一例外的是根結(jié)點就是葉結(jié)點時沒有子結(jié)點此時B樹只包含一個結(jié)(4)所有的葉結(jié)點在同一(5)有k個子結(jié)點的非根結(jié)點恰好包含k-1個關(guān)鍵補充考研內(nèi) (1)(2鍵碼沒有重復(fù)，父結(jié)點中的關(guān)鍵(3)B樹把（值接近）相關(guān)記錄放在同一 (4B樹保證樹中至少有一定比例的結(jié)點–這樣能夠改進(jìn)空間的利用–減少檢索和更新操作的磁 數(shù)補充考研內(nèi) B樹的一個包含j個關(guān)鍵碼，+1個指針的結(jié)點的一般形式為：其中Ki是關(guān)鍵碼值Pi是指向包括Ki到Ki+1之間的關(guān)鍵碼 的指針還有指針嗎補充考研內(nèi) 2-3樹=3階B18 45204520補充考研內(nèi) 交替的兩步過–1根結(jié)點讀出來，在根結(jié)點所包含的關(guān)找到則檢索成–2則，確定要查的關(guān)鍵碼值是在某個Ki如果pi指向外部空結(jié)點，表示檢索失補充考研內(nèi) 設(shè)B樹的高度為–獨根樹高為可能需要進(jìn)行h次讀盤補充考研內(nèi) 1到最底層2)若溢出，則結(jié)點 3父結(jié)點也溢出，則繼 補充考研內(nèi) 18

3階B232320204550補充考研內(nèi) 18 232345204520補充考研內(nèi) m=3，葉結(jié) ，把52提升到父結(jié)結(jié)1823232020455052補充考研內(nèi) 引起3階B樹根結(jié) 182323451920 5045補充考研內(nèi) 葉5045補充考研內(nèi) 第二結(jié) 20232023455045補充考研內(nèi) 根結(jié)點裂181823 45 50補充考研內(nèi) 上 關(guān)鍵碼19的過程有10次對B樹的訪外操其中讀盤3次（a、c、寫盤7次（g、g’、c、c’、a、a’、這里不考慮對主數(shù)據(jù)文件的訪外操作，也不考慮申請新磁盤塊的開銷t根結(jié)

4814 14

45補充考研內(nèi)45索時讀入的結(jié)點在后向上時不讀盤次數(shù)與查找相最少寫盤次數(shù)：一–不，寫出這個關(guān)鍵碼所到的結(jié)補充考研內(nèi) 一 總共h層，每層都需 （包括根一個非根結(jié)點要向磁盤寫出2結(jié)點，根結(jié)點（最后一次）要寫出3個結(jié)點= 結(jié)點向下讀盤次數(shù) 非根結(jié)點時寫盤 根結(jié)點時寫盤次=h+2(h-1)+3=補充考研內(nèi) 刪除的關(guān)鍵碼不在葉結(jié)點補充考研內(nèi) 刪除的關(guān)鍵碼在葉結(jié)點刪除后關(guān)鍵碼個數(shù)不小直接刪關(guān)鍵碼個數(shù)小

/如果兄弟結(jié)點關(guān)鍵碼個數(shù)不等

/(結(jié)點中的一個關(guān)鍵碼要做相應(yīng)變化)如果兄弟結(jié)點關(guān)鍵碼個數(shù)等合

/補充考研內(nèi) 819535 819535 108110115補充考研內(nèi) b

c1204

刪除120h溢向左借關(guān)鍵15681 351115681 351110811011118 補充考研內(nèi) b25

c

刪除150i溢鄰借關(guān)鍵借不到，h,i合108110 35108110 3511134

補充考研內(nèi) a

h,i合并成為c溢出，向左鄰借關(guān)鍵到，c25

50

11

35

108110

146156補充考研內(nèi) 是B樹的一種變在葉結(jié)點 信息的–所有的關(guān)鍵碼均出現(xiàn)在葉結(jié)點補充考研內(nèi) m階B+樹的結(jié)構(gòu)定義如下(1)每個結(jié)點至多有m空，或者獨空，或者獨(3)根至少有兩個子結(jié)點(4)所有的葉結(jié)點在同一層

/(5)有k個子結(jié)點的結(jié)點必有k個關(guān)鍵碼補充考研內(nèi)

補充考研內(nèi) 查找應(yīng)該到葉結(jié)點–在上層已找到待查的關(guān)鍵碼，并不停 適合順序檢索（范圍檢索需要的話，每一層需要的話，每一層結(jié)點也可以順補充考研內(nèi) —

過程和B樹類補充考研內(nèi) a40 305030

80

25

35

45

55

65

75

85補充考研內(nèi) t4040 4070b

805080752530752530

5155

35

45

55

65

85補充考研內(nèi) 補充考研內(nèi) a40a4070e510b2030fg35c5060i55d80h4548j65k75l85補充考研內(nèi)沿a、d、k查找，找到葉結(jié)父結(jié)點d中原分界碼80刪d結(jié)點下溢借左鄰c的關(guān)鍵碼，c和d的關(guān)鍵碼平4060c50父結(jié)點a中的分界碼4060c50a 2030 70 5102535454855658085補充考研內(nèi) 葉結(jié)點中關(guān)鍵碼數(shù)目與非葉的不非葉結(jié)點構(gòu)成B葉的階與B+樹一例如，葉結(jié)點階 階 1012

18192021

2530

333637

4045

4850補充考研內(nèi) VSAM(VirtualStorageAccess虛 存取方B+樹的應(yīng)一種索引順序文件的組織– 設(shè)備無關(guān) 單位是“邏輯”補充考研內(nèi) 索引控制域……順序集

數(shù)據(jù)集控制區(qū)間

VSAM文件結(jié)構(gòu)補充考研內(nèi) 11.4.1B11.4.2B+ 數(shù)12.2廣義表 管補充考研內(nèi) –動態(tài)數(shù)組可以在程序運行才分配內(nèi)存空補充考研內(nèi) 基本概念（續(xù)數(shù)組（Multi-array）是向量的擴(kuò)–向量的向量就組成 數(shù)–可以表示為ELEMnn

補充考研內(nèi) 二二維數(shù)三維數(shù)d1[1..3],d2[1..5],d3[1..5]分別為3個補充考研內(nèi) –以行為主序（也稱為“行優(yōu)先–以列為主序（也稱為“列優(yōu) 補充考研內(nèi) Pascal補充考研內(nèi)

……………

……am5

…補充考研內(nèi) C/C++、Pascal行優(yōu)先排最右的下從右向最后最左的下補充考研內(nèi) a1111aa1111a112a12122a213 2a2232a2m3┇………… … …a2mn ……補充考研內(nèi)FORTRAN列優(yōu)先排最左的下從左向最后最右的下例如對于三維數(shù)組a[1..k1..m的元素axyz可以如下排列補充考研內(nèi)

1

2…k11 a1212 …a1m1m … …ak12 … …┇ …ak1n … …補充考研內(nèi) 數(shù)組ELEMA[d1d

j1d2 jn1dnjn

,0])

[i

jikki1補充考研內(nèi) 三角矩陣：上三角、下三對稱矩對角矩稀疏矩補充考研內(nèi) 一維數(shù)組list[0..(n2+n)/2-list[(i2+i)/2+0007500010900180622 補充考研內(nèi) 元素滿足性質(zhì)ai,j=aj,i，0<=（i,–例如無向圖的相鄰矩其下三角的值，對稱于一維數(shù)組sa[0..n(n+1)/2-

1506 –sa[k]和矩陣元ai,j之間存在著一一對

j(

i,當(dāng)iki(i

j,當(dāng)i 補充考研內(nèi) 對角矩陣是指所有的非零元素都集中在線及以它為中心的其他對角線上。如|i-j|>1，那么數(shù)組元素a[i][j]=0a0,0a0a0,0a000an-1,n-2an-1,n-an-2,n-補充考研內(nèi) 非零元素非常少，且分布不規(guī)律的矩 11 補充考研內(nèi) 稀疏因在m×n的矩陣中，有t個非零元素，則稀疏子為

m–當(dāng)這個值小于0.05時，可以認(rèn)為是稀疏矩三元組(i,j,aij)：輸入/輸出常i是該元素的行j是該元素的列aij是該元素補充考研內(nèi) 鏈表有兩組鏈表組行和列的指針序每個結(jié)點都包含兩個指針：同一行的后繼，同一列的后0 0∧行∧∧∧ ∧∧∧ ∧頭∧∧∧∧補充考研內(nèi) A[c1..d1c3..d3]，B[c3..d3c2..d2],C＝A×B(Cij＝∑Aikfor(i=c1;i<=d1;i++)for(j=c2;j<=d2;j++){sum=0;

for(k=c3;k<=d3;sum=sum+C[i，j]=}補充考研內(nèi) p=d1-c1+1，m=d3-c3+1，n=d2-；A為p×m的矩陣，B為m×n的矩，乘得的結(jié)果C為p×n的矩經(jīng)典矩陣乘法所需要的時間代價補充考研內(nèi)

2

6 -

0

0

- 4

4列鏈表頭指行列鏈表頭指行針 0∧ ∧1 12∧0 ∧ 2-∧

∧ 補充考研內(nèi) A為p×m的矩陣，B為m×n的矩，乘得的結(jié)果C為p×n的矩矩陣B中列向量的非零元素個數(shù)最多總執(zhí)行時間降低為經(jīng)典矩陣乘法所補充考研內(nèi) 2n一元多項2n

a1

a2

anniainii補充考研內(nèi) 廣義表 管廣義管補充考研內(nèi) 基本概廣義表的各種類廣義表的周游算補充考研內(nèi) 回顧線性–線性表的每個元素都具有相同的數(shù)據(jù)類–L＝（x0，x1，…，xi，…，xn-補充考研內(nèi) L＝（x0，x1，…，xi，…，xn-L是廣義表的名n為長每個xi（0≤i≤n-1）是L的成–可以是單個元素，即原子（atom–也可以是一個廣義表，即子表補充考研內(nèi) L＝（x0，x1，…，xi，…，xn-表頭head表尾tail（x1，…，xn-–規(guī)模更小的有利補充考研內(nèi) 純表（pure–從根結(jié)點到任何葉結(jié)點只有一條路–也就是說任何一個元素（原子、子表）出現(xiàn)一(x1,(x1,(y1,(a1,a2),y3),x3,(z1補充考研內(nèi) 廣義表的各種類型（續(xù)特例：循環(huán)表（即遞歸特例：循環(huán)表（即遞歸表(((a,b)),((a,b),c,d),(d,e,f,g),(f會在表 多次出 –如果沒 回路圖 對應(yīng)于 個

(L1:(a,b),(L1,c,L2:(d)),(e,L3:(f,g)),L3補充考研內(nèi)

廣義表的各種類型（續(xù)循環(huán)–包含回(L1:(L2:(L1,a)),(L2,L3:(b)),(L3,(L1:(L2:(L1,a)),(L2,L3:(b)),(L3,c),cdab補充考研內(nèi) 補充考研內(nèi)圖再入表純表(樹)線性–廣義表是線性與樹形結(jié)構(gòu)的推廣義表應(yīng)–函數(shù)的調(diào)用關(guān)–內(nèi)存空間 關(guān)–LISP語補充考研內(nèi) 廣義 typedefenum{ATOM,LIST}ATOM0：單元素；LIST1：子typedefstructTAGtag;union{ElemTypeGLNode 子表頭指結(jié)

TAG0data/TAG0data/補充考研內(nèi) 廣義 結(jié)點的廣義表–在刪除結(jié)點的時候會出現(xiàn)問刪除結(jié)點data就必須進(jìn)行鏈調(diào)∧11∧111010∧0∧00∧補充考研內(nèi) 廣義 增加頭指針，簡化刪除 操1111∧∧01∧01∧∧0000重入表，尤其是循環(huán)–mark標(biāo)志位——圖的因補充考研內(nèi) 11∧1∧1-1∧111∧11∧1-∧1-0d--0c∧----0b∧--0a補充考研內(nèi) -1111-1111∧-0d1-0d1∧-1-10c∧-11∧--11∧-0b∧-0a1-0a1∧-1-1∧補充考研內(nèi) (L1:(L1:(L2:(a,L1)),Lx:(L2,L3:(b)),Ly:(L3,c),L4:(d,L4))∧1∧b01-∧1a0-1∧1d01----∧111--1∧0c∧補充考研內(nèi) 內(nèi)存管理存在的問可利用空間的動態(tài)分配和回伙伴系失敗處理策略和無用單元回補充考研內(nèi) 動態(tài)內(nèi)存分–new和內(nèi)存管理技鏈表、廣義補充考研內(nèi) 內(nèi)存管理最基本的問–分 空–回收被“釋放” 空碎片問的壓無用單元收–無用單元：可以回收而沒有回收的空–內(nèi)存泄漏memoryleak程序員忘記delete已經(jīng)不再使用的指補充考研內(nèi) 虛 虛擬地址空 物理內(nèi)存地0-4k- 8k- 12k-16k- 20k- 24k-28k-32k- 36k-

0-12k-16k-溢出發(fā)生后，把–選擇最近不使用的那些結(jié)補充考研內(nèi) 器看成一組變長塊數(shù)–一些塊是已分配空閑塊，形成可利用空間分配和回newp從可利用空間分deletep把p指向的數(shù)據(jù)塊返回可利用空間不夠，則求助于失敗策補充考研內(nèi)

補充考研內(nèi) template<classElem>classLinkNode{staticLinkNode //可利用空間表頭指Elem //結(jié)點LinkNode*next; em&val,LinkNode*p);LinkNode(LinkNode*p=NULL);//構(gòu)造函數(shù)void*operatornew(size_t重載new運算符voidoperatordelete(void*p);//重載delete運算符補充考研內(nèi) templateclassElem>void*LinkNode<Elem>::operatorif(avail==NULL) return::newLinkNode; //利用系統(tǒng)的new分配空LinkNode<Elem>*temp=avail;//從可利用空間表中配avail=avail-return}補充考研內(nèi) template<classElem>voidLinkNode<Elem>::operatordelete(void*p){((LinkNode<Elem>*)p)->next=avail;avail=(LinkNode<Elem>}補充考研內(nèi) 可利用空間表：單鏈表new即棧的刪除操delete即棧 操直接 系統(tǒng)的new和delete操作符，需要強(qiáng)制用“::newp”和“::deletep”–例如，程序運行完畢時，把avail所占用的補充考研內(nèi) L單鏈L單鏈表1單鏈表2

靜態(tài)

單鏈表可利用

單鏈表可可利用動動 后后區(qū)區(qū)S靜態(tài)S補充考研內(nèi) 變?？衫梅吱C找到其長度大于等于申請長度的結(jié)–從中截取合適的回–考慮剛剛被刪除的結(jié)點空間能否與鄰接合–以便能滿足后來的較大長度結(jié)點的分配補充考研內(nèi) 塊標(biāo)記位度