typedef enum(branch,left}NodeType; 与B树相比，对B树不仅可以从根结点开始按关 typedef struct BPNode 键字随机查找，而且可以从最小关键字起，按叶子结点 的链接顺序进行顺序查找。在B树上进行随机查找、插 {NodeTag tag;r结点标志y 入、 删除的过程基本上和B树类似。 nt keynum;P结点中关键字的个数司 在B+树上进行随机查找时，若非叶子结点的关键字 struct BTNode *parent:指向父结点的指针 等于给定的K值，并不终止，而是继续向下直到叶子结 点（只有叶子结点才存储记录），即无论查找成功与否， KeyType key[M+1];r组关键字向量key[O]未用 都走了一条从根结点到叶子结点的路径。 B树的插入仅仅在叶子结点上进行。当叶子结点中 union pointer 的关键字个数大于时，“分裂”为两个结点，两个结点 (struct BTNode 'ptr[M+1j:P子树指针向量 中所含有的关键字个数分别是L(m+1)2和(m+1)/21, RecType*recptr[M+1);"recptr[o]味用t 且将这两个结点中的最大关键字提升到父结点中，用来 替代原结点在父结点中所对应的关键字。提升后父结点 ptrType:P用联合体定义子树指针和记录指针 又可能会分裂，依次类推。 BPNode §9.4散列技术 §9.4.1散列表的概念 鲁压缩映象： 上述查找均是基于k©y的比较，由判定树可证明，在 平均和最坏情况下所需的此较次数的下界是： ◆例于：设影德出粗店 Ign+0(1) 总片数：10,000张 要突破此界，就不能只依懒于比较来进行， 僧还：500人次海天 记录，（电话号码，姓名，住址，），Ky为7位电话号网 直核寻址：须保需1000万个记录 59.4.1散列表的禄念 但奖际只曼大于500即可，量多1万个记录 ●直接寻址：当结点的k©y和存储位置间建立某种关系时， 令一搬信淀 无须比较即可找到结点的存储位置。 金集：可能发生的关量字填合，即关整字的取值氯合 例如，若500个结点的keys取值为1~500间互不相 实际发生第K:实际常要存销的关轴字集合 同的整数，则keys可作为下标，将其存储到T[1.500]之 中，寻址时间为0(1)。 :KN<U,当豪T的规横取U浪费空间，有时塔至无法实现 :T的视模一般取O(K),但压输存雠后失去了直核寻址的功能 3 S9.41散列表的概念 S9.4.1散列表的概念 ■数列(hash)西数h 不下你出来来丝之周立一个对应关系，养金集快前到印m南 。敢列(hash)西败h ◆神突碰撞：若k≠k,有h(k)=h(k) h:U-{0,1,,m-1) hash 存储地址 ◆同义词：发生冲突的两个关键字互为同义词（相对于） 寸k,eU,hk)∈{0,1，m-1】 集合 集合 女能完全避免冲突吗？ ◆数列液：T 须满足：①U川≤m②选择合适的hah函数 ◆数列地址（散列值）：散列西数值k T0.m- g散列(hashing), 0 否则只能设计好的使冲突尽可能少 ◆解决冲突：须确定处理冲突的方法 h(k2) ◆装填因子：冲突的频繁程度除了与的好坏相关，还与表的 填满程度相关 h(k,尸h(k a=n/m.0≤a≤1 m-1 35 66 31 typedef enum{branch, left} NodeType ; typedef struct BPNode { NodeTag tag ; /* 结点标志 */ int keynum ; /* 结点中关键字的个数 */ struct BTNode *parent ; /* 指向父结点的指针 */ KeyType key[M+1] ; /* 组关键字向量,key[0]未用 */ union pointer { struct BTNode *ptr[M+1] ; /* 子树指针向量 */ RecType *recptr[M+1] ; /* recptr[0]未用 */ }ptrType ; /* 用联合体定义子树指针和记录指针 */ }BPNode ; 32 与B_树相比，对B+树不仅可以从根结点开始按关 键字随机查找，而且可以从最小关键字起，按叶子结点 的链接顺序进行顺序查找。在B+树上进行随机查找、插 入、删除的过程基本上和B_树类似。 在B+树上进行随机查找时，若非叶子结点的关键字 等于给定的K值，并不终止，而是继续向下直到叶子结 点(只有叶子结点才存储记录) ， 即无论查找成功与否， 都走了一条从根结点到叶子结点的路径。 B+树的插入仅仅在叶子结点上进行。当叶子结点中 的关键字个数大于m时，“分裂”为两个结点，两个结点 中所含有的关键字个数分别是⎣(m+1)/2⎦和⎡ (m+1)/2⎤ ， 且将这两个结点中的最大关键字提升到父结点中，用来 替代原结点在父结点中所对应的关键字。提升后父结点 又可能会分裂，依次类推。 33 § 9.4 散列技术 上述查找均是基于key的比较，由判定树可证明，在 平均和最坏情况下所需的比较次数的下界是： lgn＋O(1) 要突破此界，就不能只依赖于比较来进行。 § 9.4.1 散列表的概念 „ 直接寻址：当结点的key和存储位置间建立某种关系时， 无须比较即可找到结点的存储位置。 例如，若500个结点的keys取值为1～500间互不相 同的整数，则keys可作为下标，将其存储到T[1..500]之 中，寻址时间为O (1)。 34 § 9.4.1 散列表的概念 „ 压缩映象： ™ 例子：设影像出租店 总片数：10,000张 借还：500人次/每天 记录：（电话号码，姓名，住址，…）, Key为7位电话号码 直接寻址：须保留1000万个记录 但实际只要大于500即可，最多1万个记录 ™ 一般情况 全集U：可能发生的关键字集合，即关键字的取值集合 实际发生集K：实际需要存储的关键字集合 ∵ |K| << |U|，当表T的规模取|U|浪费空间，有时甚至无法实现 ∴ T的规模一般取O(K), 但压缩存储后失去了直接寻址的功能 35 § 9.4.1 散列表的概念 „ 散列（hash）函数h 在keys和表地址之间建立一个对应关系h，将全集U映射到T[0..m-1]的 下标集上： h：U→{ 0, 1, … , m-1 } ∀ki ∈U，h(ki ) ∈ { 0,1,…,m-1 } ™ 散列表: T ™ 散列地址（散列值）：散列函数值h(ki ) ™ 散列（hashing）： 关键字 集合 存储地址 集合 hash U. . . K k1 . . . . k2 . . . k3. h(k2) h(k1)=h(k3) 0 m-1 T[0..m-1] 36 § 9.4.1 散列表的概念 „ 散列（hash）函数h ™冲突(碰撞): 若ki ≠kj ，有h(ki ) ＝ h(kj ) ™同义词：发生冲突的两个关键字互为同义词(相对于h) ™能完全避免冲突吗？ 须满足：① |U|≤m ② 选择合适的hash函数 否则只能设计好的h使冲突尽可能少 ™解决冲突： 须确定处理冲突的方法 ™装填因子：冲突的频繁程度除了与h的好坏相关，还与表的 填满程度相关 α＝n/m， 0≤ α ≤ 1