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

(23,a4)

(20,a9)

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

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

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

4814 14

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

/如果兄弟結點關鍵碼個數不等

/(結點中的一個關鍵碼要做相應變化)如果兄弟結點關鍵碼個數等合

/補充考研內 819535 819535 108110115補充考研內 b

c1204

刪除120h溢向左借關鍵15681 351115681 351110811011118 補充考研內 b25

c

刪除150i溢鄰借關鍵借不到，h,i合108110 35108110 3511134

補充考研內 a

h,i合并成為c溢出，向左鄰借關鍵到，c25

50

11

35

108110

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

/(5)有k個子結點的結點必有k個關鍵碼補充考研內

補充考研內 查找應該到葉結點–在上層已找到待查的關鍵碼，并不停 適合順序檢索（范圍檢索需要的話，每一層需要的話，每一層結點也可以順補充考研內 —

過程和B樹類補充考研內 a40 305030

80

25

35

45

55

65

75

85補充考研內 t4040 4070b

805080752530752530

5155

35

45

55

65

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

18192021

2530

333637

4045

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

數據集控制區間

VSAM文件結構補充考研內 11.4.1B11.4.2B+ 數12.2廣義表 管補充考研內 –動態數組可以在程序運行才分配內存空補充考研內 基本概念（續數組（Multi-array）是向量的擴–向量的向量就組成 數–可以表示為ELEMnn

補充考研內 二二維數三維數d1[1..3],d2[1..5],d3[1..5]分別為3個補充考研內 –以行為主序（也稱為“行優先–以列為主序（也稱為“列優 補充考研內 Pascal補充考研內

……………

……am5

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

1

2…k11 a1212 …a1m1m … …ak12 … …┇ …ak1n … …補充考研內 數組ELEMA[d1d

j1d2 jn1dnjn

,0])

[i

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

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

j(

i,當iki(i

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

m–當這個值小于0.05時，可以認為是稀疏矩三元組(i,j,aij)：輸入/輸出常i是該元素的行j是該元素的列aij是該元素補充考研內 鏈表有兩組鏈表組行和列的指針序每個結點都包含兩個指針：同一行的后繼，同一列的后0 0∧行∧∧∧ ∧∧∧ ∧頭∧∧∧∧補充考研內 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]=}補充考研內 p=d1-c1+1，m=d3-c3+1，n=d2-；A為p×m的矩陣，B為m×n的矩，乘得的結果C為p×n的矩經典矩陣乘法所需要的時間代價補充考研內

2

6 -

0

0

- 4

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

∧ 補充考研內 A為p×m的矩陣，B為m×n的矩，乘得的結果C為p×n的矩矩陣B中列向量的非零元素個數最多總執行時間降低為經典矩陣乘法所補充考研內 2n一元多項2n

a1

a2

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

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

廣義表的各種類型（續循環–包含回(L1:(L2:(L1,a)),(L2,L3:(b)),(L3,(L1:(L2:(L1,a)),(L2,L3:(b)),(L3,c),cdab補充考研內 補充考研內圖再入表純表(樹)線性–廣義表是線性與樹形結構的推廣義表應–函數的調用關–內存空間 關–LISP語補充考研內 廣義 typedefenum{ATOM,LIST}ATOM0：單元素；LIST1：子typedefstructTAGtag;union{ElemTypeGLNode 子表頭指結

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

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

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

靜態

單鏈表可利用

單鏈表可可利用動動 后后區區S靜態S補充考研內 變常可利用分–找到其長度大于等于申請長度的結–從中截取合適的回–考慮剛剛被刪除的結點空間能否與鄰接合–以便能滿足后來的較大長度結點的分配補充考研內 塊標記位度