课件-10补充12.2广义表和存储管理

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补充考研内 变常可利用分–找到其长度大于等于申请长度的结–从中截取合适的回–考虑刚刚被删除的结点空间能否与邻接合–以便能满足后来的较大长度结点的分配补充考研内 块标记位度