数据结构：二叉查找树、AVL、B-Tree、B+Tree

- 日理万妓 2021-11-14 12:02 281阅读 0赞

**目录**

1、二叉查找树

2、AVL树（平衡二叉查找树）

3、平衡多路查找树（B-Tree）

4、B+Tree

--------------------

# 1、二叉查找树 #

二叉树是一棵树，其中每个节点都不能有多于两个的儿子。二叉查找树要求所有的项都能够排序。

二叉查找树需要满足如下特点：

①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；  
           ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；  
           ③左、右子树本身又各是一棵二叉排序树。

![ç´¢å¼][20160202203355523]

对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3次

树的节点为N，则树的平均深度为 O(logN)。

二叉查找树可以任意地构造，同样是2,3,5,6,7,8这六个数字，也可以按照下图的方式来构造：

![ç´¢å¼][20160202203448944]

但是这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称AVL树。

二叉树java伪代码实现

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5oYW8xMjAz_size_16_color_FFFFFF_t_70][]

本身的点、左边点和右边点组成。

缺点：在25万次随机 insert / remove 对操作后，树明显的不平衡。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5oYW8xMjAz_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5oYW8xMjAz_size_16_color_FFFFFF_t_70 2][]

# 2、AVL树（平衡二叉查找树） #

AVL 树是带有平衡条件的二叉查找树。

一棵 AVL 树是其每个节点的左子树和右子树的高度最多差 1 的二叉查找树（空树的高度定义为 -1）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5oYW8xMjAz_size_16_color_FFFFFF_t_70 3][]

如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它们的示意图如下：

![20160202203648148][]  
这四种失去平衡的姿态都有各自的定义：   
LL：LeftLeft，也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。

RR：RightRight，也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。

LR：LeftRight，也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。

RL：RightLeft，也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。

AVL树失去平衡之后，可以通过旋转使其恢复平衡。下面分别介绍四种失去平衡的情况下对应的旋转方法。

LL的旋转。LL失去平衡的情况下，可以通过一次旋转让AVL树恢复平衡。步骤如下：

将根节点的左孩子作为新根节点。  
将新根节点的右孩子作为原根节点的左孩子。  
将原根节点作为新根节点的右孩子。  
LL旋转示意图如下：

![ç´¢å¼][20160202204113994]  
RR的旋转：RR失去平衡的情况下，旋转方法与LL旋转对称，步骤如下：

将根节点的右孩子作为新根节点。  
将新根节点的左孩子作为原根节点的右孩子。  
将原根节点作为新根节点的左孩子。  
RR旋转示意图如下：

![ç´¢å¼][20160202204207963]  
LR的旋转：LR失去平衡的情况下，需要进行两次旋转，步骤如下：

围绕根节点的左孩子进行RR旋转。  
围绕根节点进行LL旋转。  
LR的旋转示意图如下：

![20160202204257369][]  
RL的旋转：RL失去平衡的情况下也需要进行两次旋转，旋转方法与LR旋转对称，步骤如下：

围绕根节点的右孩子进行LL旋转。  
围绕根节点进行RR旋转。  
RL的旋转示意图如下：

![ç´¢å¼][20160202204331073]

# 3、平衡多路查找树（B-Tree） #

二叉查找树、AVL（平衡二叉查找树）这两个数据结构都是把整个数据结构存储到计算机的主存中。如果数据更多装不下主存，那么就意味着把数据结构放到磁盘上。此时，因为大 O 模型不再适用，所以导致游戏规则发生了变化。

大 O 分析假设所有的操作耗时都是相等的。数据存储到了磁盘也就意味着产生 I/O操作，这是时间就不会相等了。

**例证磁盘之慢**：一台 500 — MIPS的机器可能每秒执行 5亿条指令。磁盘访问的速度依赖于转动磁盘和移动磁头的时间，假设磁盘1分钟转 7200转，转1转就是 1/120 秒，即 8.3毫秒，一次磁盘访问就相当于执行了 40万条指令的时间。

粗略计算后发现，磁盘访问的代价太高了。

因此，为了节省一次磁盘访问，我们可以增加计算，磁盘访问次数的减少，意味着查询速度的大幅提升。

**推导 M叉树**

假设有一千万条数据，每条记录是 256字节。假设这些数据不能都装入主存，还是上面那个机器，假设我们用了 1/20的资源。这样，在1秒内，我们可以执行 2500万次指令，或者执行 6次磁盘访问。

不平衡的二叉查找树是一个灾难。在最坏情形下它具有线性的深度，从而可能需要 1 千万次磁盘访问。

平均来看，一次成功的查找可能需要 1.38 log N 次磁盘访问，由于 log 1000 0000 约等于 24，因此平均一次查找需要 32次磁盘访问，或 5秒的时间。在一棵典型的随机构造的树中，预期深度要深 3 倍，大概需要 100 次磁盘访问，需要 16秒的时间。

AVL 树好一些，1.44 log N的最坏情况不可能发生，典型的情形是非常接近于 log N，平均将使用大约 25 次磁盘访问，需要的时间是 4 秒。

显然，不管是二叉查找树，还是AVL树，耗时都很多，不太可行。

使用二叉查找树、AVL树都受到 log N的限制，最少也要这个深度，导致耗时比较大，如果 建立 一棵 完全 M 叉树，随着 M的增大，树的深度会明显减小，耗时也会减小。**这种 M叉树的实现方式就是 B树**。

系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB。  
而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。

InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组\[key, data\] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。

**阶为 M 的 B 树是一棵具有以下特征的树**：  
1. 每个节点最多有m个孩子。   
2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。   
3. 若根节点不是叶子节点，则至少有2个孩子   
4. 所有叶子节点都在同一层，且不包含其它关键字信息   
5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）   
6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1   
7. ki(i=1,…n)为关键字，且关键字升序排序。   
8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

![ç´¢å¼][20160202204827368]

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程：

1.  根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2.  比较关键字29在区间（17,35），找到磁盘块1的指针P2。
3.  根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4.  比较关键字29在区间（26,30），找到磁盘块3的指针P2。
5.  根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
6.  在磁盘块8中的关键字列表中找到关键字29。

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。**B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率**。

# 4、B+Tree #

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而**非叶子节点上只存储key值信息**，这样可以大大加大每个节点存储的key值数量，**降低B+Tree的高度**。

B+Tree相对于B-Tree有几点不同：

1.  非叶子节点只存储键值信息。
2.  所有叶子节点之间都有一个链指针。
3.  数据记录都存放在叶子节点中。

将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

![20160202205105560][]

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10^3 \* 10^3 \* 10^3 = 10亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

数据库中的B+Tree索引可以分为**聚簇索引**和**非聚簇索引索引**。上面的B+Tree示例图在数据库中的实现即为**聚簇索引**，**聚簇索引**的B+Tree中的叶子节点存放的是整张表的行记录数据。**非聚簇索引索引**与**聚簇索引**的区别在于**非聚簇索引索引**的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过**非聚簇索引索引**来查询数据时，InnoDB存储引擎会遍历**非聚簇索引索引**找到主键，然后再通过主键在**聚簇索引索引**中找到完整的行记录数据。

引用：

[https://blog.csdn.net/u013235478/article/details/50625677][https_blog.csdn.net_u013235478_article_details_50625677]

数据结构与算法分析 java语言描述

[20160202203355523]: /images/20211114/fd05ef6f9cec46fabfef34996647a6c0.png
[20160202203448944]: /images/20211114/89bc1913cfa743afbd8d4fc7ff80b4f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5oYW8xMjAz_size_16_color_FFFFFF_t_70]: /images/20211114/968ab39d85874c45b742cfbf91018712.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5oYW8xMjAz_size_16_color_FFFFFF_t_70 1]: /images/20211114/c9759d02dcfa4a34b2b2ae1d18596e4b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5oYW8xMjAz_size_16_color_FFFFFF_t_70 2]: /images/20211114/dcb95e11a32445dcbe41086cd42d005e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3J1YW5oYW8xMjAz_size_16_color_FFFFFF_t_70 3]: /images/20211114/9cc191c7c16242bb8e3216ed01b440a6.png
[20160202203648148]: /images/20211114/1f6a05c664ad4b3daae7e8175cabda8b.png
[20160202204113994]: /images/20211114/a2a68c2711a24c04ae1f15b017d19a6e.png
[20160202204207963]: /images/20211114/828bd4e58e784f12a0b1585ed748c61f.png
[20160202204257369]: /images/20211114/3d45a245ee6e4c498876bbba72024e9f.png
[20160202204331073]: /images/20211114/5949969c87d2486895cb1a984c452116.png
[20160202204827368]: /images/20211114/31bfa678fe0b4f06b4d34c0defae9c6e.png
[20160202205105560]: /images/20211114/419b7aa8cd0d4138b42d9cded3854550.png
[https_blog.csdn.net_u013235478_article_details_50625677]: https://blog.csdn.net/u013235478/article/details/50625677