计算机系统应用教程网站

网站首页 > 技术文章 正文

数据结构:二叉树、B-Tree、B+Tree、红黑树

btikc 2024-11-06 16:43:55 技术文章 5 ℃ 0 评论

二叉树

1.所有非叶子结点至多拥有两个子节点(Left和Right);

2.所有结点存储一个关键字;

3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

二叉树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;

否则,如果查询关键字比结点关键字小,就进入左子节点;如果比结点关键字大,就进入

右子节点;如果左子节点或右子节点的指针为空,则报告找不到相应的关键字;

从算法逻辑上来讲,二叉树的查找速度和比较次数都是最小的 ,但是像数据库中数据要持久化在磁盘上,每次查找都要从磁盘中通过IO拿到内存中,如果数据量大内存一次性查询,服务内存根本支撑不了,所以每次IO只读取一个层级的节点到内存中去做判断。树的高度就是IO的次数。IO次数多肯定影响效率!

要想减少IO的次数,就要将二叉树的高度降低,降低高度就意味着多叉树,我们称作为Btree(B-tree)多路搜索树。

B-Tree/Btree

是一种多路搜索树(并不是二叉的,可以让原来的二叉树变得“矮胖”---目的:高度降低):

浅蓝色的块我们称之为一个磁盘块,可以看到每个磁盘块包含几个数据项(深蓝色所示)和指针(黄色所示),红点表示是指向卫星数据的指针,指针指向的是存放实际数据的磁盘页,卫星数据就是数据库中一条数据记录。

如磁盘块1包含数据项17和35,包含指针P1、P2、P3,P1表示小于17的磁盘块,P2表示在17和35之间的磁盘块,P3表示大于35的磁盘块。

b-树的查找过程

如图所示,如果要查找数据项29,那么首先会把磁盘块1由磁盘加载到内存,此时发生一次IO,在内存中用二分查找确定29在17和35之间,锁定磁盘块1的P2指针,内存时间因为非常短(相比磁盘的IO)可以忽略不计

通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存,发生第二次IO,29在26和30之间,锁定磁盘块3的P2指针

通过指针加载磁盘块8到内存,发生第三次IO,同时内存中做二分查找找到29,结束查询,总计三次IO。

真实的情况是,3层的Btree可以表示上百万的数据,如果不是Btree这种多路搜索树,那么几乎每个数据项都要发生一次IO,那么总共需要百万次的IO,显然成本非常非常高;如果上百万的数据查找只需要三次IO,性能提高将是巨大的。

B+Tree

是B-树的变体,也是一种多路搜索树,比B-tree效率更高:

1、根节点和分支节点中不保存索引数据,只用于索引,所有数据都保存在叶子节点中。

2、所有分支节点和根节点都同时存在于子节点中,在子节点元素中是最大或者最小的元素。

3、叶子节点会包含所有的索引数据(关键字),以及指向数据记录的指针,并且叶子节点本身是根据关键字的大小从小到大顺序链接。

更直观地图

1、红点表示是指向卫星数据的指针,指针指向的是存放实际数据的磁盘页,卫星数据就是数据库中一条数据记录。

2、叶子节点中还有一个指向下一个叶子节点的next指针,所以叶子节点形成了一个有序的链表,方便遍历B+树。

搜索过程与B树的查询过程没有区别。但实际上有两点不一样:(优势)

1、首先B+树的中间节点不存储卫星数据,所以同样大小的磁盘页可以容纳更多的节点元素,如此一来,相同数量的数据下,B+树就相对来说要更加矮胖些,磁盘IO的次数更少。

2、由于只有叶子节点才保存卫星数据,B+树每次查询都要到叶子节点;而B树每次查询则不一样,最好的情况是根节点,最坏的情况是叶子节点,没有B+树稳定。

3、叶子节点形成有序链表,范围查找性能更优

如:范围查找3-11的数据:

B-树是逐个查询该范围内的数据;

B+树范围查找3-11的过程如下图:

先从上到下找到下限元素3,然后通过链表指针,依次遍历得到元素5/6/8/9/11;如此一来,就不用像B树那样一个个元素进行查找。

如:Mysql的Mysam存储引擎和Innodb存储引擎的索引的数据结构都是B+树结构,

ES的倒排索引底层结构也是B+tree。

红黑树

红黑树又称R-B Tree,全称是Red-Black Tree,红黑树是一种含有红黑结点并能自平衡的二叉查找树

如果二叉树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么二叉树的搜索性能逼近二分查找,效率还算可以;但是二叉树在经过多次插入与删除后,有可能导致不同的结构:

右边也是一个二叉树,但它的搜索性能已经是线性的了,查询效率跟链表差不多,凸显不出二分查找的优势,所以,使用二叉树还要考虑尽可能让二叉树保持左图的结构,和避免右图的结构,也就是所谓的“平衡”问题;

红黑树具有以下五个特性

(1)节点要么是红色要么是黑色

(2)根节点是黑色

(3)如果一个结点是红色的,则它的所有子结点必须是黑色的

(4)从一个结点到该结点的子孙结点的所有路径上包含相同数目的黑结点。

(5)每个叶子的节点都是黑色的空节点(NULL)

红黑树任意节点其左右子树最多相差2层红节点。所以大致上是平衡的。

当我们在对红黑树进行插入和删除等操作时,对树做了修改 可能会违背红黑树的性质。

为了保持红黑树的性质,我们可以对相关节点做一系列的调整,通过对树进行变色旋转(例如左旋右旋操作),即修改树中某些结点的颜色及指针结构,以达到对红黑树进行插入、删除结点等操作时,红黑树依然能保持它特有的性质(五点性质)。

无论是左旋还是右旋,都不会超过三次旋转

对于JDK中集合类:TreeMap、TreeSet以及jdk1.8之后的 HashMap地城都使用了 红黑树。

注:

B-Tree、B+Tree是为了减少磁盘IO提高搜索效率;

红黑树多用于内存存储,不经历IO,只要保证二叉树的平衡就保证了搜索效率。

Tags:

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

最近发表
标签列表