关于B树 B+树 B*树以及红黑树的理解 1、首先要明白为什么有了AVL树之后还会出现这么多树的变种? 可以参考这个知乎有关几种树的应用的回答:作者:王伟豪链接:https://www.zhihu.com/question//answer/来源:知乎 AVL树:平衡二叉树,一般是用平衡因子差值决定并通过旋转来实现,左右子树树高差不超过1,那么和红黑树比较它是严格的平衡二叉树,平衡条件非常严格(树高差只有1),只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少,但查找多的情况。 红黑树:平衡二叉树,通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束,确保没有一条路径会比其他路径长2倍,因而是近似平衡的。所以相对于严格要求平衡的AVL树来说,它的旋转保持平衡次数较少。用于搜索时,插入删除次数多的情况下我们就用红黑树来取代AVL。(现在部分场景使用跳表来替换红黑树,可搜索“为啥 redis 使用跳表(skiplist)而不是使用 red-black?”) B树,B+树:它们特点是一样的,是多路查找树,一般用于数据库系统中,为什么,因为它们分支多层数少呗,都知道磁盘IO是非常耗时的,而像大量数据存储在磁盘中所以我们要有效的减少磁盘IO次数避免磁盘频繁的查找。B+树是B树的变种树,有n棵子树的节点中含有n个关键字,每个关键字不保存数据,只用来索引,数据都保存在叶子节点。是为文件系统而生的。 以上几种树都是有序的,如果你采用合适的算法遍历整个数,可以得到一个有序的列表。这也是为什么如果有数据库索引的情况下,你order by你索引的值,就会速度特别快,因为它并没有给你真的排序,只是遍历树而已 Trie树:又名单词查找树,一种树形结构,常用来操作字符串。它是不同字符串的相同前缀只保存一份。相对直接保存字符串肯定是节省空间的,但是它保存大量字符串时会很耗费内存(是内存)。类似的有前缀树(prefix tree),后缀树(suffix tree),radix tree(patricia tree, compact prefix tree),crit-bit tree(解决耗费内存问题),以及前面说的double array trie。简单的补充下我了解应用前缀树:字符串快速检索,字符串排序,最长公共前缀,自动匹配前缀显示后缀。后缀树:查找字符串s1在s2中,字符串s1在s2中出现的次数,字符串s1,s2最长公共部分,最长回文串。radix tree:linux内核,nginx。 2、B 树(B-树 )、B+树 、B*树的详细解释 B树也就是我们常说的B-树,一样的,他和B+树的用法不一样 1、二叉搜索树 性质:所有非叶子结点至多拥有两个儿子(Left和Right);每个结点存储一个关键字;非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树。 搜索:从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字。 性能:如果B树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变B树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销。 2.外存储器—磁盘 计算机存储设备一般分为两种:内存储器(main memory)和外存储器(external memory)。内存存取速度快,但容量小,价格昂贵,而且不能长期保存数据(在不通电情况下数据会消失)。 外存储器—磁盘是一种直接存取的存储设备(DASD)。它是以存取时间变化不大为特征的。可以直接存取任何字符组,且容量大、速度较其它外存设备更快。 2.1磁盘的构造 磁盘是一个扁平的圆盘(与电唱机的唱片类似)。盘面上有许多称为磁道的圆圈,数据就记录在这些磁道上。磁盘可以是单片的,也可以是由若干盘片组成的盘组,每一盘片上有两个面。如下图11.3中所示的6片盘组为例,除去最顶端和最底端的外侧面不存储数据之外,一共有10个面可以用来保存信息。
当磁盘驱动器执行读/写功能时。盘片装在一个主轴上,并绕主轴高速旋转,当磁道在读/写头(又叫磁头) 下通过时,就可以进行数据的读 / 写了。 一般磁盘分为固定头盘(磁头固定)和活动头盘。固定头盘的每一个磁道上都有独立的磁头,它是固定不动的,专门负责这一磁道上数据的读/写。 活动头盘 (如上图)的磁头是可移动的。每一个盘面上只有一个磁头(磁头是双向的,因此正反盘面都能读写)。它可以从该面的一个磁道移动到另一个磁道。所有磁头都装在同一个动臂上,因此不同盘面上的所有磁头都是同时移动的(行动整齐划一)。当盘片绕主轴旋转的时候,磁头与旋转的盘片形成一个圆柱体。各个盘面上半径相同的磁道组成了一个圆柱面,我们称为柱面。因此,柱面的个数也就是盘面上的磁道数。 2.2磁盘的读/写原理和效率 磁盘上数据必须用一个三维地址唯一标示:柱面号、盘面号、块号(磁道上的盘块)。 读/写磁盘上某一指定数据需要下面3个步骤: (1) 首先移动臂根据柱面号使磁头移动到所需要的柱面上,这一过程被称为定位或查找。 (2) 如上图11.3中所示的6盘组示意图中,所有磁头都定位到了10个盘面的10条磁道上(磁头都是双向的)。这时根据盘面号来确定指定盘面上的磁道。 (3) 盘面确定以后,盘片开始旋转,将指定块号的磁道段移动至磁头下。 经过上面三个步骤,指定数据的存储位置就被找到。这时就可以开始读/写操作了。访问某一具体信息,由3部分时间组成: ● 查找时间(seek time) Ts: 完成上述步骤(1)所需要的时间。这部分时间代价最高,最大可达到0.1s左右。 ● 等待时间(latency time) Tl: 完成上述步骤(3)所需要的时间。由于盘片绕主轴旋转速度很快,一般为7200转/分(电脑硬盘的性能指标之一, 家用的普通硬盘的转速一般有5400rpm(笔记本)、7200rpm几种)。因此一般旋转一圈大约0.0083s。 ● 传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间,一般传输一个字节(byte)大概0.02us=2*10^(-8)s 磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块,同一磁道中。或者至少放在同一柱面或相邻柱面上,以求在读/写信息时尽量减少磁头来回移动的次数,避免过多的查找时间Ts。 所以,在大规模数据存储方面,大量数据存储在外存磁盘中,而在外存磁盘中读取/写入块(block)中某数据时,首先需要定位到磁盘中的某块,如何有效地查找磁盘中的数据,需要一种合理高效的外存数据结构,就是下面所要重点阐述的B-tree结构,以及相关的变种结构:B+-tree结构和B*-tree结构。 2、B-树 性质:是一种多路搜索树(并不是二叉的): 1.定义任意非叶子结点最多只有M个儿子;且M>2; 2.根结点的儿子数为[2, M]; 3.除根结点以外的非叶子结点的儿子数为[M/2, M]; 4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字) 5.非叶子结点的关键字个数=指向儿子的指针个数-1; 6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1]; 7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树; 8.所有叶子结点位于同一层;
搜索:从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点; 1.关键字集合分布在整颗树中; 2.任何一个关键字出现且只出现在一个结点中; 3.搜索有可能在非叶子结点结束; 4.其搜索性能等价于在关键字全集内做一次二分查找; 5.自动层次控制; 6.由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为lgN; 7.B-树的性能总是等价于二分查找(与M值无关),没有B树平衡的问题; 8.由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并; 3、B+树 性质:B+树是B-树的变体,也是一种多路搜索树: 1.其定义基本与B-树同,除了: 2.非叶子结点的子树指针与关键字个数相同; 3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间); 4.为所有叶子结点增加一个链指针; 5.所有关键字都在叶子结点出现;
B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在 非叶子结点命中),其性能也等价于在关键字全集做一次二分查找; B+的特性: 1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的; 2.不可能在非叶子结点命中; 3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层; 4.更适合文件索引系统; 4、B*树 是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;
B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2); B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针; B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针; 所以,B*树分配新结点的概率比B+树要低,空间使用率更高; 小结 B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点; B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中; B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中; B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3。 参考博客(包括相关原理应用的介绍以及具体的区别): https://blog.csdn.net/dazhong159/article/details/7963846 https://www.cnblogs.com/George1994/p/7008732.html 再说一点个人的理解:红黑树因为去除了严格的平衡条件(红黑树平衡的标准是最长路径长度不超过最短的二倍),并且在它的旋转保持平衡次数较少。用于搜索时,插入删除次数多的情况下我们就用红黑树来取代AVL
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/41150.html