数据结构总结---------非线性表（多叉平衡树）

逃离我推掉我的手 2022-03-15 10:34 222阅读 0赞

### 数据结构总结---------非线性表（多叉平衡树） ###

*  1.为什么会出现多叉平衡树？
 *  2.常见的多叉平衡树
 *   *  2.1 B树
     *   *  1.图解
         *  2.简介
     *  2.2 B+树
     *   *  1.图解
         *  2.简介
     *  2.3 B\*树
     *   *  1.图解

# 1.为什么会出现多叉平衡树？ #

多叉树可以降低树的深度，从而就可以达到提高查询效率的作用

# 2.常见的多叉平衡树 #

## 2.1 B树 ##

### 1.图解 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70]

### 2.简介 ###

B树应文件系统的要求而发展起来的，大量数据放在外存中，通常放在磁盘中，由于是海量数据，不可能一次调入内存。因此要多次访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以在1972年由R.Bayer和E.Macreight提出用B树作为索引组织文件，提高访问速度，减少时间，而其数据在每个节点都有存储

## 2.2 B+树 ##

### 1.图解 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 1]

### 2.简介 ###

在B树的基础上为叶子节点增加链表指针，所有关键字都在叶子节点中出现，非叶子节点作为叶子节点的索引；数据都是存储在叶子节点中的

**注：数据库的索引默认的数据结构就是采用的B+树**

## 2.3 B\*树 ##

### 1.图解 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 2]  
**注：B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟的指针**

[https://me.csdn.net/qq\_39657909][https_me.csdn.net_qq_39657909]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70]: /images/20220315/7e0b7ed3e2a74d4980d52739b24857bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 1]: /images/20220315/1716f2a8d1db4051a0d19b64f48f3a05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 2]: /images/20220315/4a0be28cd6434ee28f0fe30e14018292.png
[https_me.csdn.net_qq_39657909]: https://me.csdn.net/qq_39657909