二叉树、平衡二叉树、B- tree、B+ tree 基本概念

雨点打透心脏的1/2处 2022-05-20 06:59 295阅读 0赞

# **1 二叉树**  #

二叉树binary tree是指每个节点最多含有两个子树的树结构。

**特点：**

1.所有节点最多拥有两个子节点，即度不大于2

2.左子树的键值小于根的键值，右子树的键值大于根的键值。

因为二叉树只是定义了简单的结构，所以存在多种深度可能，导致二叉树的效率低，所以引入了平衡二叉树。

![70][]

# 2 平衡二叉树 #

## 2.1 avl树 ##

平衡二叉树，基于avl算法，即是avl树（avl tree）

**特点：**

1.符合二叉树的条件下

2.任何节点的两个子树的高度最大差为1

如果在avl 树，中进行插入和删除节点操作，可能导致avl树失去平衡，那么可以通过旋转重新达到平衡。因此我们说的二叉树也称自平衡二叉树。

## 2.2 红黑树 ##

红黑树和avl树类似，都是在进行插入和删除操作时通过特定的操作保持二叉树的平衡，从而获得较高的查找性能。

在java中TreeSet，TreeMap的底层就是用的这个方法。

**特点：**

1.节点是红色或黑色

2.根节点是黑色

3.叶子节点（nil,空节点）是黑色

4.每个红色节点的两个子节点都是黑色

# 3 B-tree #

B通常理解成是Balance的意思，B- tree 就是B树。

B树是平衡**多路查找树（有多个查找路径，不止2个）**，是一种平衡的多叉树。因为B树是平衡树，每个节点到叶子节点的高度都是相同的，这样可以保证B树的查询是稳定的。

使用B tree 可以显著减少定位记录时所经历的中间过程，从而快速定位，加快存取速度。

与二叉树相比，B-tree利用多个分支（二叉树只有2个分支）节点，**减少了获取记录时所经历的节点数**，从而达到节省存取时间的目的。

**特点：**

1.每个节点的关键字增多了，特别是B树应用到数据库中的时候。

数据库充分利用了磁盘块的原理（磁盘数据的存储采用的是块的形式进行存储，每个块的大小一般为4k,每次去取数据的时候，就是取出这个4k的大小，而不是只取出你想要的大小。就是说每次IO的时候，同一磁盘块的数据都是一次性提取出来）。把树的节点关键字增多后，树的层级比原来二叉树的层级少了，这样就可以减少数据查找的次数 ，降低复杂度了。

2.所有的页节点都在同一层上

# B+ tree #

B+tree 是在 B- tree基础上的优化，使其更适应存储索引结构

B- tree的结构中，每个节点不仅包括数据的key值，也包括data值。而每一页的存储空间都是有限的，如果data数据较大的时候，会导致，每一页中存储的key比较少，当存储的数据量比较大时，同样会导致B- tree的查询深度很大，增加磁盘IO次数，进而影响查询效率

B+ tree中，非叶子节点上只存储key的信息，这样可以加大每一页中存储key的数量，降低B+ tree的高度。

**特点（与B- tree相比）：**

1.非叶子节点只存储key信息

2.所有叶子节点之间有一个链指针

3.B+的非叶子节点只进行数据的索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样。

4.B+树的应用场景主要是数据库索引结构，数据库的查询有时候可能一次多条，如果分布在不同的层（树的层级），那么在取出数据后，还需要做排序。而在一个层级上，且有指针连接各个叶子节点也使得查询效率更高。

参考：

[TreeMap][]

[70]: /images/20220520/1c1ed9b7584a41dea2bc7a6c42382264.png
[TreeMap]: https://blog.csdn.net/mazhimazh/article/details/19028311

发表评论取消回复

表情：

评论列表（有 0 条评论，295人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉搜索树、平衡二叉树

一、二叉搜索树这里我们不用太多书面化的语言来定义，笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字，不便于读者理解。

阳光穿透心脏的1/2处/ 2023年10月18日 22:26/ 0 赞/ 82 阅读

相关二叉树——110. 平衡二叉树

1 题目描述给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

女爷i/ 2023年10月08日 16:12/ 0 赞/ 40 阅读

相关彻底搞懂这些：二叉树、平衡二叉树、B-Tree、B+Tree

[背景][Link 1] 一般说MySQL的索引，都清楚其索引主要以B+树为主，此外还有Hash、RTree、FullText。本文简要说明一下MySQL的B+Tree索

浅浅的花香味﹌/ 2023年10月01日 22:16/ 0 赞/ 12 阅读

相关二叉查找树，平衡二叉树，B树，B+树区别

二叉查找树对于树的每个节点，其左子树上每个节点都比它小，其右子树上每个节点的值都比它大 -------------------- 平衡二叉树（AVL树）对于树的每个

川长思鸟来/ 2023年01月06日 01:16/ 0 赞/ 182 阅读

相关二叉树、平衡二叉树、B-Tree、B+Tree 说明

B+Tree 结构是从二叉查找树，平衡二叉树和B-Tree这三种数据结构演化来的，他们之前的区别上面已经介绍过，现在大致的总结下，如下：　　1，二叉查找树是基于二分查

迷南。/ 2023年01月03日 14:10/ 0 赞/ 175 阅读

相关二叉树，完全二叉树，满二叉树，二叉排序树，平衡二叉树，红黑树，B数，B-树，B+树，B*树（二）

二叉树，完全二叉树，满二叉树，二叉排序树，平衡二叉树，红黑树，B数，B-树，B+树，B\树（一）： [http://blog.csdn.net/yuxin6866/ar

左手的ㄟ右手/ 2022年07月17日 02:09/ 0 赞/ 310 阅读

相关二叉树，完全二叉树，满二叉树，二叉排序树，平衡二叉树，红黑树，B数，B-树，B+树，B*树（一）

二叉树二叉树：二叉树是每个节点最多有两个子树的树结构；是n(n>=0)个结点的有限集合，它或者是空树（n=0），或者是由一个根结点及两颗互不相交的、分别称为左子

谁借莪１个温暖的怀抱￠/ 2022年07月17日 02:09/ 0 赞/ 284 阅读

相关平衡二叉树、B树、B+树、B*树

平衡二叉树、B树、B+树、B\树 1、平衡二叉树（1）由来：平衡二叉树是基于二分法的策略提

忘是亡心i/ 2022年05月29日 06:12/ 0 赞/ 222 阅读

相关二叉树、平衡二叉树、B- tree、B+ tree 基本概念

1 二叉树二叉树binary tree是指每个节点最多含有两个子树的树结构。特点： 1.所有节点最多拥有两个子节点，即度不大于2

雨点打透心脏的1/2处/ 2022年05月20日 06:59/ 0 赞/ 296 阅读

相关二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树概念的简单区分

文章目录 1、二叉树（Binary Tree） 2、二叉搜索树（Binary Search Tree） 3、平衡二叉树（AVL T

一时失言乱红尘/ 2021年10月19日 09:38/ 0 赞/ 427 阅读