修🐶的家

总有一条蜿蜒在童话镇里七彩的河

  menu
50 文章
0 浏览
2 当前访客
ღゝ◡╹)ノ❤️

数据结构

B+树、B树、 红黑树的区别

B+树和B树区别:

1.B+树中只有叶子节点会带有指向记录的指针,而B树则所有节点都带有,在内部节点出现的索引项不会再出现在叶子节点中。

2.B+树中所有叶子节点都是通过指针连接在一起,而B树不会。

B+树的优点:

1.非叶子节点不会带上指向记录的指针,这样,一个块中可以容纳更多的索引项,一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。

2.叶子节点之间通过指针来连接,范围扫描将十分简单,而对于B树来说,则需要在叶子节点和内部节点不停的往返移动。具体的来讲,如何想扫描一次所有数据,对于b+树来说,可以从因为他们的叶子结点是连在一起的,所以可以横向的遍历过去。而对于b-树来说,就这能中序遍历了。

B树的优点:
对于在内部节点的数据,可直接得到,不必根据叶子节点来定位。

红黑树和B树应用场景有何不同?

为什么要设计红黑树?

红黑树的规则:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

  平衡树(AVL)更平衡,结构上更加直观,时间效能针对读取而言更高,但是维护起来比较麻烦!!!(插入和删除之后,都需要rebalance)。但是,红黑树通过它规则的设定,确保了插入和删除的最坏的时间复杂度是O(log N) 。

设计红黑树的目的

就是解决平衡树的维护起来比较麻烦的问题,红黑树,读取略逊于AVL,维护强于AVL,每次插入和删除的平均旋转次数应该是远小于平衡树。红黑树其实就是平衡树的一种,复杂的定义和规则,最后都是为了保证树的平衡性。因为树的查找性能取决于树的高度,让树尽可能平衡,就是为了降低树的高度。

小结:

能用平衡树的地方,就可以用红黑树。用红黑树之后,读取略逊于AVL,维护强于AVL。

红黑树和 b+树的用途有什么区别?

1.红黑树多用在内部排序,即全放在内存中的,STL的map和set的内部实现就是红黑树。

2.B+树多用于外存上时,B+也被成为一个磁盘友好的数据结构。

为什么b+磁盘友好?

1.磁盘读写代价更低
2.树的非叶子结点里面没有数据,这样索引比较小,可以放在一个blcok(或者尽可能少的blcok)里面。避免了树形结构不断的向下查找,然后磁盘不停的寻道,读数据。这样的设计,可以降低io的次数。

3.查询效率更加稳定
4.非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

5.遍历所有的数据更方便
B+树只要遍历叶子节点就可以实现整棵树的遍历,而其他的树形结构 要中序遍历才可以访问所有的数据。

/*

B+树是在B树的基础上基础上进行改造,它的数据都在叶子节点,同时叶子节点之间还加了指针形成链表

*/

为什么mysql索引使用b+树而不使用红黑树?

  b+树就是为文件存储而生的。如果数据库文件存储在主存中我认为两种结构的查询速度差距不是很大,因为主存的查找速度非常快。而数据库文件实际存储在磁盘中,定位一行信息需要查找该行文件所在柱面号,磁盘号,扇区号,页号这个阶段是很耗费时间的。每一次的定位请求意味着要做一次IO操作,也意味着成倍的时间消耗。因此减少IO查询的次数是提高查询性能的关键。而IO的查询次数就是索引树的高度,高度越低查询的次数越少。同样的结点次数红黑树的高度最多为2log(n+1),而B+树的高度最多为(logt (n+1)/2)+1,随着t增大高度会更小,IO次数也会减少。

**为什么要设计成多路呢? **

是为了进一步的降低树的高度,路数越多,树的高度就越低

所以,如果实在内存中,红黑树比B树的效率更高,但涉及到磁盘操作,B树就更优了。

为什么要这么设计呢? (B+树)

这是和业务场景相关的,数据库中 Select 数据,不一定只选一条,很多时候会选多条,比如按照 ID 排序后选 10 条。如果是多条的话,B树需要做局部的中序遍历,可能还要跨层访问,而B+树由于所有数据都在叶子节点,不用跨层,同时由于有链表结构,只需要找到首尾,通过链表就能把所有数据取出来了。

Java中的HashMap底层结构 为什么8的时候转换为红黑树具体说一下,为什么不直接用红黑树 链表红黑树的查 询效率

红黑树高度2log(n+1)

每一个节点要么红色要么黑色.

根节点是黑色.

所有叶子节点NIL是黑色.

红色节点的左右孩子必定是黑色节点.

从任何一个节点出发,并达到这个节点下面的所有叶子节点的所有路径.这些路径中,含有的黑色节点个数相同.

红黑树和AVL树的区别

平衡二叉树:

平衡二叉树全称平衡二叉搜索树,也叫AVL树。是一种自平衡的树。

AVL树也规定了左结点小于根节点,右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。AVL树的查找稳定,查找、插入、删除的时间复杂度都为O(logN),但是由于要维持自身的平衡,所以进行插入和删除结点操作的时候,需要对结点进行频繁的旋转。

AVL树每一个节点只能存放一个元素,并且每个节点只有两个子节点。当进行查找时,就需要多次磁盘IO,(数据是存放在磁盘中的,每次查询是将磁盘中的一页数据加入内存,树的每一层节点存放在一页中,不同层数据存放在不同页。)这样如果需要多层查询就需要多次磁盘IO。为了解决AVL树的这个问题,就出现了B树

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

红黑树:

红黑树也叫RB树,RB-Tree。是一种自平衡的二叉查找树,它的节点的颜色为红色和黑色。它不严格控制左、右子树高度或节点数之差小于等于1。也是一种解决二叉查找树极端情况的数据结构。

红黑树规定了:

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点(NIL节点)。

4 每个红色节点的两个子节点都是黑色。也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点)。

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树在查找方面和AVL树操作几乎相同。但是在插入和删除操作上,AVL树每次插入删除会进行大量的平衡度计算,红黑树是牺牲了严格的高度平衡的优越条件为代价,它只要求部分地达到平衡要求,结合变色,降低了对旋转的要求,从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。

相比于BST,因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度,所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的,这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高,所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多,但是他们的查找效率都是O(logN),所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。

B+树深度:

索引字段占内存大小,指针占内存大小(6字节 6Byte,或者6B)

1、先看看b+树结构

下面看一颗树

第一行中,1,320为索引数据排序后的数据范围,这里叫键值key,1-30,320- 32 对应的是页指针,指向下一页

  • b+树非叶子节点存放的都是key+nest指针。叶子节点存放数据

*在mysql索引b+树中,非叶子节点键值数=子节点数

2、计算

在mysql索引中索引页默认大小16k

SHOW VARIABLES LIKE 'innodb_page_size';

一页可以理解成一个节点(非叶子节点或者叶子节点)

先假设一个变量

每行数据量大小1K

索引字段Int:4字节(4byte)

bigint:8byte

verchar:一个字符占3byte

那么一页可以最多有多少子节点呢(bigint而言)

16384/(8+6) = 1170

在叶子节点中每页16K,每行数据1K,那么就是16条记录

所以b+树深度和数据库数量的关系

1170(n-1)次方 * 16

深度=3的b+树

1170 1170 16 = 21902400(2千万数据)**

所以一般数据库b+深度也就3-5层

解决哈希冲突方法

1)链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。

链地址法适用于经常进行插入和删除的情况

2)开放地址法

这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。

3)再哈希法

这种方法同样是按照按某种方法探测哈希表中的其他存储单元,直到找到空位置为止。具体来看是同时构造多个不同的哈希函数:

Hi=RH1(key) i=1,2,…,k

Hi=RH2(key) i=1,2,…,k

4)建立公共溢出区

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。


标题:数据结构
作者:hanmoonhan
地址:https://www.hanmoonhan.club/articles/2023/04/23/1682257059036.html