哪些数据库用b 树，二叉树在计算机科学与技术中的应用有哪些

来源：整理时间：2023-11-20 08:12:34 编辑：黑码技术手机版

本文目录一览

1，二叉树在计算机科学与技术中的应用有哪些
2，Btree的B树
3，什么是B树索引

1，二叉树在计算机科学与技术中的应用有哪些

霍夫曼编码：这是一种数据压缩方法，利用一棵霍夫曼树（本质为二叉树）来压缩一组数据。优先级队列：它使用一棵二叉树来记录集合中元素的优先级，并将其排序，为解决问题提供更好的方案。事件调度：主要使用二叉搜索树，这能够使得查找信息更加高效。数据库系统：主要使用B树，这能够使插入和删除操作更加高效。用户界面：在图形用户界面中，窗口按树形结构组织，如windows系统。文件系统：文件按树形结构组织，如windows系统。人工智能：比如棋类这种逻辑类的游戏，可以把步骤生成决策树。以上如果需要详细了解，可直接百度相关名词。

你好，很高兴为你答疑。你所说的情况是满二叉树行数和总节点数的规律是 2^n-1 所以七层的就是 2^7-1 = 127 另外各层的节点数规律为 2^(n-1) 若问题解决还望采纳支持，若有疑问欢迎讨论。

二叉树在计算机科学与技术中的应用有哪些

2，Btree的B树

另外还有一种与此类似的树结构叫B+树，像 Berkerly DB , sqlite , mysql 数据库都使用了B+树算法处理索引。B+和B-（即B）是因为每个结点上的关键字不同。一个多一个，一个少一个。对于B+树，其结点结构与B-tree相同，不同的是各结点的关键字和可以拥有的子结点数。如m阶B+树中，每个结点至多可以拥有m个子结点。非根结点至少有[m/2]个子结点，而关键字个数比B-tree多一个，为[m/2]~m。这两种处理索引的数据结构的不同之处：1。B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。2。因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。3。B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时间复杂度对某建成的树是固定的。

1970年，r.bayer和e.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为b树，其定义如下：按照翻译,b 应该是banlance的简称.b+和b-是因为每个结点上的关键字不同.一个多一个,一个少一个. 一棵m阶的b树满足下列条件： ⑴ 树中每个结点至多有m个孩子； ⑵ 除根结点和叶子结点外，其它每个结点至少有m/2个孩子； ⑶ 若根结点不是叶子结点，则至少有2个孩子； ⑷ 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息； ⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字。在b树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。 b树中的一个包含n个关键字，n+1个指针的结点的一般形式为：（n,p0,k1,p1,k2,p2,…,kn,pn）其中，ki为关键字，k1<…

Btree的B树

3，什么是B树索引

B+树是一种树数据结构，常见于数据库与档案系统之中。B+树能够使资料保持有序，并拥有均匀的对数处理时间的插入和删除动作。B树的元素通常会自底向上插入，有别于多数自顶向下插入的二叉树。B+ 树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。B+ 背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B+ 树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树(常简称为2-3 树)中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。B+ 树的创造者 Rudolf Bayer 没有解释B代表什么。最常见的观点是B代表平衡(balanced)，因为所有在叶子节点在树中都在相同的级别上。B也可能代表Bayer，或者是波音(Boeing)，因为他曾经工作于波音科学研究实验室。节点结构在 B+ 树中的节点通常被表示为一组有序的元素和子指针。除了根之外的每个节点都包含最少 L 个元素最多 U 个元素，对于任意的 L 和 U 有最多 U+1 个子指针。对于所有内部节点，子指针的数目总是比元素的数目多一个。因为所有叶子都在相同的高度上，节点通常不包含确定它们是叶子还是内部节点的方式。每个内部节点的元素充当分开它的子树的分离值。例如，如果内部节点有三个子节点(或子树)则它必须有两个分离值或元素 a1 和 a2。在最左子树中所有的值都小于 a1，在中间子树中所有的值都在 a1 和 a2 之间，而在最右子树中所有的值都大于 a2。算法查找查找以典型的方式进行，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用二分查找来确定这个位置。插入节点要处于违规状态，它必须包含在可接受范围之外数目的元素。首先，查找要插入其中的节点的位置。接着把值插入这个节点中。如果没有节点处于违规状态则处理结束。如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则建立一个新根节点。为了使它工作，元素的最小和最大数目典型的必须选择为使最小数不大于最大数的一半。删除首先，查找要删除的值。接着从包含它的节点中删除这个值。如果没有节点处于违规状态则处理结束。如果节点处于违规状态则有两种可能情况: 它的兄弟节点，就是同一个父节点的子节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。注解假定 L 是节点允许拥有子节点的最小数目，而 U 是最大数目。则每个节点总是有在 L 和 U 之间(包含它们在内)个子节点，除了一个例外: 根节点有从2到U(包含它们在内)个子节点。换句话说，根节点豁免于低边界限制，而拥有它自己的低边界2。这允许树持有小数目的元素。根有一个子节点没有意义，因为附着在这个子节点上的子树可以简单的附着在根节点上。允许根节点没有子节点也是不需要的，因为没有元素的树典型的表示为没有根节点。

先从数据结构的角度来答。题主应该知道b-树和b+树最重要的一个区别就是b+树只有叶节点存放数据，其余节点用来索引，而b-树是每个索引节点都会有data域。这就决定了b+树更适合用来存储外部数据，也就是所谓的磁盘数据。从mysql（inoodb）的角度来看，b+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。那么mysql如何衡量查询效率呢？磁盘io次数，b-树（b类树）的特定就是每层节点数目非常多，层数很少，目的就是为了就少磁盘io次数，当查询数据的时候，最好的情况就是很快找到目标索引，然后读取数据，使用b+树就能很好的完成这个目的，但是b-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘io次数（磁盘io一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，io次数增多，一次io多耗时啊！），而b+树除了叶子节点其它节点并不存储数据，节点小，磁盘io次数就少。这是优点之一。另一个优点是什么，b+树所有的data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。至于mongodb为什么使用b-树而不是b+树，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以json格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，上面所述的优点2需求就没那么强烈了，其次mysql由于使用b+树，数据都在叶节点上，每次查询都需要访问到叶节点，而mongodb使用b-树，所有节点都有data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于mysql（但侧面来看mysql至少平均查询耗时差不多）。总体来说，mysql选用b+树和mongodb选用b-树还是以自己的需求来选择的。

什么是B树索引