建设银行e路护航官方网站登陆,wordpress 最大上传,深圳网站建设制作优化,网站费用构成B树1.1B树的定义B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数#xff0c;阶数表示了一个结点最多有多少个孩子结点#xff0c;一般用字母m表示阶数。当m取2时#xff0c;就是我们常见的二叉搜索树。一颗m阶的B树定义如下#xff1a;1)每个结点最… B树1.1B树的定义B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数阶数表示了一个结点最多有多少个孩子结点一般用字母m表示阶数。当m取2时就是我们常见的二叉搜索树。一颗m阶的B树定义如下1)每个结点最多有m-1个关键字。2)根结点最少可以只有1个关键字。3)非根结点至少有Math.ceil(m/2)-1个关键字。4)每个结点中的关键字都按照从小到大的顺序排列每个关键字的左子树中的所有关键字都小于它而右子树中的所有关键字都大于它。5)所有叶子结点都位于同一层或者说根结点到每个叶子结点的长度都相同。上图是一颗阶数为4的B树。在实际应用中的B树的阶数m都非常大(通常大于100)所以即使存储大量的数据B树的高度仍然比较小。每个结点中存储了关键字(key)和关键字对应的数据(data)以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。但为了方便描述除非特别说明后续文中就用key来代替(key, value)键值对这个整体。在数据库中我们将B树(和B树)作为索引结构可以加快查询速速此时B树中的key就表示键而data表示了这个键对应的条目在硬盘上的逻辑地址。1.2B树的插入操作插入操作是指插入一条记录即(key, value)的键值对。如果B树中已存在需要插入的键值对则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。1)根据要插入的key的值找到叶子结点并插入。2)判断当前结点key的个数是否小于等于m-1若满足则结束否则进行第3步。3)以结点中间的key为中心分裂成左右两部分然后将这个中间的key插入到父结点中这个key的左子树指向分裂后的左半部分这个key的右子支指向分裂后的右半部分然后将当前结点指向父结点继续进行第3步。下面以5阶B树为例介绍B树的插入操作在5阶B树中结点最多有4个key,最少有2个keya)在空树中插入39b)继续插入2297和41c)继续插入53插入后超过了最大允许的关键字个数4所以以key值为41为中心进行分裂结果如下图所示分裂后当前结点指针指向父结点满足B树条件插入操作结束。当阶数m为偶数时需要分裂时就不存在排序恰好在中间的key那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可d)依次插入132140同样会造成分裂结果如下图所示。e)依次插入3027, 33 363534 2429结果如下图所示。f)插入key值为26的记录插入后的结果如下图所示。当前结点需要以27为中心分裂并向父结点进位27然后当前结点指向父结点结果如下图所示。进位后导致当前结点(即根结点)也需要分裂分裂的结果如下图所示。分裂后当前结点指向新的根此时无需调整。g)最后再依次插入key为17,28,29,31,32的记录结果如下图所示。在实现B树的代码中为了使代码编写更加容易我们可以将结点中存储记录的数组长度定义为m而非m-1这样方便底层的结点由于分裂向上层插入一个记录时上层有多余的位置存储这个记录。同时每个结点还可以存储它的父结点的引用这样就不必编写递归程序。一般来说对于确定的m和确定类型的记录结点大小是固定的无论它实际存储了多少个记录。但是分配固定结点大小的方法会存在浪费的情况比如key为28,29所在的结点还有2个key的位置没有使用但是已经不可能继续在插入任何值了因为这个结点的前序key是27,后继key是30,所有整数值都用完了。所以如果记录先按key的大小排好序再插入到B树中结点的使用率就会很低最差情况下使用率仅为50%。1.3B树的删除操作删除操作是指根据key删除记录如果B树中的记录中不存对应key的记录则删除失败。1)如果当前需要删除的key位于非叶子结点上则用后继key(这里的后继key均指后继记录的意思)覆盖要删除的key然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步2)该结点key个数大于等于Math.ceil(m/2)-1结束删除操作否则执行第3步。3)如果兄弟结点key个数大于Math.ceil(m/2)-1则父结点中的key下移到该结点兄弟结点中的一个key上移删除操作结束。否则将父结点中的key下移与当前结点及它的兄弟结点中的key合并形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针指向这个新结点。然后当前结点的指针指向父结点重复上第2步。有些结点它可能即有左兄弟又有右兄弟那么我们任意选择一个兄弟结点进行操作即可。下面以5阶B树为例介绍B树的删除操作5阶B树中结点最多有4个key,最少有2个keya)原始状态b)在上面的B树中删除21删除后结点中的关键字个数仍然大于等2所以删除结束。c)在上述情况下接着删除27。从上图可知27位于非叶子结点中所以用27的后继替换它。从图中可以看出27的后继为28我们用28替换27然后在28(原27)的右孩子结点中删除28。删除后的结果如下图所示。删除后发现当前叶子结点的记录的个数小于2而它的兄弟结点中有3个记录(当前结点还有一个右兄弟选择右兄弟就会出现合并结点的情况不论选哪一个都行只是最后B树的形态会不一样而已)我们可以从兄弟结点中借取一个key。所以父结点中的28下移兄弟结点中的26上移,删除结束。结果如下图所示。d)在上述情况下接着32结果如下图。当删除后当前结点中只key而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并成为一个新的结点当前结点的指针指向父结点。结果如下图所示。当前结点key的个数满足条件故删除结束。e)上述情况下我们接着删除key为40的记录删除后结果如下图所示。同理当前结点的记录数小于2兄弟结点中没有多余key所以父结点中的key下移和兄弟(这里我们选择左兄弟选择右兄弟也可以)结点合并合并后的指向当前结点的指针就指向了父结点。同理对于当前结点而言只能继续合并了最后结果如下所示。合并后结点当前结点满足条件删除结束。B树2.1 B树的定义各种资料上B树的定义各有不同一种定义方式是关键字个数和孩子结点个数相同。这里我们采取维基百科上所定义的方式即关键字个数比孩子结点个数小1这种方式是和B树基本等价的。上图就是一颗阶数为4的B树。除此之外B树还有以下的要求。1)B树包含2种类型的结点内部结点(也称索引结点)和叶子结点。根结点本身即可以是内部结点也可以是叶子结点。根结点的关键字个数最少可以只有1个。2)B树与B树最大的不同是内部结点不保存数据只用于索引所有数据(或者说记录)都保存在叶子结点中3) m阶B树表示了内部结点最多有m-1个关键字(或者说内部结点最多有m个子树)即有n个关键字就有n个子数阶数m同时限制了叶子结点最多存储m-1个记录4)内部结点中的key都按照从小到大的顺序排列对于内部结点中的一个key左树中的所有key都小于它右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。5)每个叶子结点都存有相邻叶子结点的指针叶子结点本身依关键字的大小自小而大顺序链接。2.2 B树的插入操作1)若为空树创建一个叶子结点然后将记录插入其中此时这个叶子结点也是根结点插入操作结束。2)针对叶子类型结点根据key值找到叶子结点向这个叶子结点插入记录。插入后若当前结点key的个数小于等于m-1则插入结束。否则将这个叶子结点分裂成左右两个叶子结点左叶子结点包含前m/2个记录右结点包含剩下的记录将第m/21个记录的key进位到父结点中(父结点一定是索引类型结点)进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点然后执行第3步。3)针对索引类型结点若当前结点key的个数小于等于m-1则插入结束。否则将这个索引类型结点分裂成两个索引结点左索引结点包含前(m-1)/2个key右结点包含m-(m-1)/2个key将第m/2个key进位到父结点中进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点然后重复第3步。下面是一颗5阶B树的插入过程5阶B数的结点最少2个key最多4个key。a)空树中插入5b)依次插入81015c)插入16插入16后超过了关键字的个数限制所以要进行分裂。在叶子结点分裂时分裂出来的左结点2个记录右边3个记录中间key成为索引结点中的key分裂后当前结点指向了父结点(根结点)。结果如下图所示。当然我们还有另一种分裂方式给左结点3个记录右结点2个记录此时索引结点中的key就变为15。d)插入17e)插入18插入后如下图所示当前结点的关键字个数大于5进行分裂。分裂成两个结点左结点2个记录右结点3个记录关键字16进位到父结点(索引类型)中将当前结点的指针指向父结点。当前结点的关键字个数满足条件插入结束。f)插入若干数据后g)在上图中插入7结果如下图所示当前结点的关键字个数超过4需要分裂。左结点2个记录右结点3个记录。分裂后关键字7进入到父结点中将当前结点的指针指向父结点结果如下图所示。当前结点的关键字个数超过4需要继续分裂。左结点2个关键字右结点2个关键字关键字16进入到父结点中将当前结点指向父结点结果如下图所示。当前结点的关键字个数满足条件插入结束。2.3 B树的删除操作如果叶子结点中没有相应的key则删除失败。否则执行下面的步骤1)删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1删除操作结束,否则执行第2步。2)若兄弟结点key有富余(大于Math.ceil(m-1)/2 – 1)向兄弟结点借一个记录同时用借到的key替换父结(指当前结点和兄弟结点共同的父结点)点中的key删除结束。否则执行第3步。3)若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点并删除父结点中的key(父结点中的这个key两边的孩子指针就变成了一个指针正好指向这个新的叶子结点)将当前结点指向父结点(必为索引结点)执行第4步(第4步以后的操作和B树就完全一样了主要是为了更新索引结点)。4)若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1则删除操作结束。否则执行第5步5)若兄弟结点有富余父结点key下移兄弟结点key上移删除结束。否则执行第6步6)当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点重复第4步。注意通过B树的删除操作后索引结点中存在的key不一定在叶子结点中存在对应的记录。下面是一颗5阶B树的删除过程5阶B数的结点最少2个key最多4个key。a)初始状态b)删除22,删除后结果如下图删除后叶子结点中key的个数大于等于2删除结束c)删除15删除后的结果如下图所示删除后当前结点只有一个key,不满足条件而兄弟结点有三个key可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9删除结束。d)删除7删除后的结果如下图所示当前结点关键字个数小于2(左)兄弟结点中的也没有富余的关键字(当前结点还有个右兄弟不过选择任意一个进行分析就可以了这里我们选择了左边的)所以当前结点和兄弟结点合并并删除父结点中的key当前结点指向父结点。此时当前结点的关键字个数小于2兄弟结点的关键字也没有富余所以父结点中的关键字下移和两个孩子结点合并结果如下图所示。声明 转载自B树和B树的插入、删除图文详解
