B树-文档资料

1、1算法导论算法导论B树树 B树的定义 B树的基本操作 从B树删除键胡学钢、吴共庆 2 基于磁盘的数据结构 至今为止，搜索树是仅仅在内存里面的数据结构。 前提: 内存可以容纳搜索树中的数据集 (包括树的负载) 反例: 银行中的交易数据 每天 1 GB 每天增加 1GB 内存 ( 电源故障？) 使用二级存储设备 (穿孔卡, 硬盘, 磁带,等等.) 要求: 使搜索树结构必须能使用二级存储设备。3硬盘 I 在 实际的系统中, 我们要处理内存中不能装载的数据。 从硬盘读取数据元素:查找磁头等待该磁头转过必要的扇区传输 数据4硬盘 II 大量数据，而且存取缓大量数据，而且存取缓慢慢! 定位一页需要很长时间

2、 (搜索时间 加上旋转延时 5-10ms), 读取很快比较适合以页页读写数据 (或者块) ，大小为2-16 Kb 。5算法分析 基于磁盘的算法的运行时间主要的测量的指标有 计算时间 (CPU) 磁盘存取数目 顺序读取 随机读取一次处理一个数据元素的常规内存算法不能直接“移植”到二级存储上。6原则 数据结构中的指针不再指向内存，而是指向文件中的位置。 如果 x 是指向一个对象的指针 如果 x 在内存中 keyx 指向它 否则 DiskRead(x) 将对象从磁盘读入内存 (DiskWrite(x) 将其写回磁盘)7原则 (2) 一个典型的工作模式0102xapointertosomeobject

3、03DiskRead(x)04operationsthataccessand/ormodifyx05DiskWrite(x)/omittedifnothingchanged06otheroperations,onlyaccessnomodify078B树定义 节点 x 包括域 nx: 节点中键的数目 key1x keynxx: 递增顺序的键 leafx: 如果是叶子节点为真, 如果是内部节点为假 如果是内部节点, 那么 c1x, , cnx+1x: 指向孩子 键分开了子树中键的范围。如果 ki 是子树 cix 中的任意一个键，那么 ki keyix ki+19B树定义 (2) 每个叶子的深度相

4、同 除了根节点外的所有节点有 t 到 2t 之间个孩子 (i.e. 从t1 到 2t1之间个键). B树 的度度为 t. 根节点有 0 到 2t 之间个孩子 (i.e. 从 0 到 2t1 之间个键)10B树:定义 (3) 我们仅仅关心键 B树是平衡树 节点为高扇出 (很多孩子) C G MA BJ K LQ R SN OY ZU VT XPD E F11 高度为 h的B树 T, 以下对高度的限制成立：B树的高度1log2tnh111 (1)221hihinttt 1t - 1t - 1t - 1t - 1t - 1ttt - 1t - 1t - 1011222t深度#节点数12二叉树与B树对

5、比100010001000100010011000100010001001100110011 节点1000 节点1001 节点,1,001,000 节点1,002,001 节点,1,002,001,000 键 B树节点的大小取决于页的大小。 一页 一个节点. 一个高度为2的 B树包含 1百万个键! 二叉树的高度和B树是对数的B树:对数的基, 比如1000 二叉树: 对数的基为 213红黑树和B树 比较红黑树和B树 高度均为 O(log n) 红黑树对数的基为2 B树的基为1000 树的高度相关的差异是 lg t 当 t=2时, B树是 2-3-4树 (它表示的是红黑树)!14B树操作 B树的实

6、现应该支持以下操作 搜索搜索 (简单)创建创建 一棵空树 (很简单)插入插入 (复杂)删除删除 (复杂)15搜索n():int n(x) 节点中x键的数目keyi() keyi(X) x中的第i个键 ci() ci(x) the -th x中第i个指针leaf():bool - leaf(x) 如果x 是叶子为真BTreeSearch(x,k)01i102whileinxandkkeyix03ii+104ifinxandk=keyixthen05return(x,i)06ifleafxthen08returnNIL09elseDiskRead(cix)10returnBTtreeSearch(

7、cix,k)16创建一棵空树 空B树 = 创建根 & 写到磁盘!BTreeCreate(T)01xAllocateNode();02leafxTRUE;03nx0;04DiskWrite(x);05rootTx17分裂节点 节点被填满，到达它的最大容量 2t 1 在插入一个新的键之前，我们必须”腾出地方”，也就是说 分裂节点18分裂节点 (2)P Q R S T V WT1T8. N W .y = cixkeyi-1xkeyixx. N S W .keyi-1xkeyixxkeyi+1xP Q RT V Wy = cixz = ci+1x 结果: 一个键 x 移动到父亲节点，同时增加了两个t-

8、1个键的节点19分裂节点 (2)BTreeSplitChild(x,i,y)01zAllocateNode()02leafzleafy03nzt-104forj1tot-105keyjzkeyj+ty06ifnotleafythen07forj1tot08cjzcj+ty09nyt-110forjnx+1downtoi+111cj+1xcjx12ci+1x z13forjnxdowntoi14keyj+1xkeyjx15keyixkeyty16nxnx+117DiskWrite(y)18DiskWrite(z)19DiskWrite(x)x: 父节点y: x的孩子，要分裂的节点i: x中的索引

9、z: 新节点P Q R S T V WT1T8. N W .y = cixkeyi-1xkeyixx20分裂:运行时间 局部操作不会遍历树 Q(t) CPU时间, 因为两个循环运行 t 次 3 次I/O 21插入键 递归进行，从根开始递归的向叶子遍历。 在下降到树的下一层之前，保证节点的键 2t 1 22插入键 (2) 特殊情况: 根为空 (BtreeInsert)BTreeInsert(T)01rrootT02ifnr=2t1then03sAllocateNode()05rootTs06leafsFALSE07ns008c1sr09BTreeSplitChild(s,1,r)10BTreeI

10、nsertNonFull(s,k)11elseBTreeInsertNonFull(r,k)23 将根节点分裂需要创建新的节点 树从顶部，而不是底部增长。分裂根A D F H L N PT1T8.rootTrA D FL N PHrootTsr24插入键 BtreeNonFull 试图 将键 k 插入到节点 x, 当这个函数调用的时候，要这个假设假设节点不为满不为满 BTreeInsert 和 BTreeInsertNonFull中的递归保证这一假设总是成立!25插入键: 伪代码BTreeInsertNonFull(x,k)01inx02ifleafxthen03whilei1andkkeyi

11、x04keyi+1xkeyix05ii-106keyi+1x=k07nxnx+108DiskWrite(x)09elsewhilei1andkkeyixthen16ii+117BTreeInsertNonFull(cix,k)插入叶子内部节点: 遍历树26插入: 举例G M P XA C D EJ KR S T U VN OY ZG M P XA B C D EJ KR S T U VN OY ZG M P T XA B C D EJ KQ R SN OY ZU V初始化树 (t = 3)插入B插入Q 27插入: 举例 (2)G MA B C D EJ K LQ R SN OY ZU VT X

12、PC G MA BJ K LQ R SN OY ZU VT XPD E F插入L插入F28插入: 运行时间 磁盘 I/O: O(h),在BTreeInsertNonFull的递归调用期间因为仅进行 O(1) 的磁盘存取 CPU: O(th) = O(t logtn) 任何时间内存中有 O(1) 的磁盘页29删除键 递归进行, 从根开始递归的向叶子递归遍历。 在下降到树的下一层之前，保证节点包含 t 个键 (cf. 插入 2t 1 个键) BtreeDelete 将删除分为三个阶段/情景情况 1: 在叶子节点找到键 k情况 2: 在内部节点找到键 k 情况 3: 怀疑键 k 更低层的节点30 情

13、况 1: 如果键k在节点x中, 并且x是叶子, 从x中删除k删除键 (2)C G MA BJ K LQ R SN OY ZU VT XPD E F初始化树C G MA BJ K LQ R SN OY ZU VT XPD EF 被删除: 情况 1x31删除键 (3)C G LA BJ KQ R SN OY ZU VT XPD EM 被删除: 情况 2a 情况 2: 如果键 k 在节点x中, 并且x 不是叶子, 从x中删除 ka) 在节点x的孩子中如果前于k 的子节点y 至少有 t 个键, 那么找到以y为根的子树中的k的前继k 。递归的删除 k, 将中 x的 k 替换为 k.b)对后继节点z进行对

14、称的处理xy32删除键 (4) 如果 y 和 z 都仅有 t 1 个键,将k和z的内容合并到并到 y, 所以 x 失去了 k 和指向z的指针, 并且现在 y 有了 2t 1 个键. 释放 z 并且递归的从y中删除 k.C LA BD E J KQ R SN OY ZU VT XPG 被删除: 情况 2cy = y + z - kx - k33删除键 分布 沿着树下降: 如果在当前节点x找不到k ,查找必定包含k的子树cix. 如果cix仅有t 1个键，需要采取措施保证我们下降碰到的节点的大小至少是t. 我们可能碰到两种情况. 如果 cix 仅有 t-1 个键, 但是一个兄弟至少有 t 个键,

15、从x移动一个键给 cix使它多一个键, 从cix的相邻的左右兄弟移动一个键给 x, 并且从兄弟中移动适当的孩子给cix 分布分布 34删除键 分布(2)C L P T XA BE J KQ R SN OY ZU Vcixx兄弟删除 BB 被删除:E L P T XA CJ KQ R SN OY ZU V. k . . k A Bcixx. k . . k AcixB 35删除键 合并 如果 cix 和 cix的两个兄弟都有 t 1个键, 将ci和一个兄弟合并, 包括从x 向下移动一个键到新合并的节点，并且成为这个节点的中间键x. l m .l k m . A Bx. l k m. . l m AB cix36删除键 合并 (2)树的高度tree shrinks in heightD 被删除: C L P T XA BE J KQ R SN OY ZU VC LA BD E J KQ R SN OY ZU VT XP删除 Dcix兄弟37删除: 运行时间 大多数键在叶子,因此删除大多发生在这里! 大多数情况下删除从树上向下走一遍就够了 磁盘 I/O: O(h), 在递归调用中仅产生 O(1) 的磁盘操作 CPU: