数据结构——树与二叉树

谁践踏了优雅 2022-03-26 03:52 256阅读 0赞

## 一、引言 ##

在介绍索引前，要先了解一下数据结构——树。因为MySQL中常用的InnoDB和MyISAM引擎中，索引的存储结构用到的数据结构就是B+树，所以有必要要了解一下。

## 二、树与二叉树 ##

树是一种数据结构，其中一个元素可以有两个或者多个数据元素，具有一对多的特点，通常用树结构来存储文件。如果每个元素最多有两个结点，这种树结构则叫做二叉树。下面来介绍一下树中的几个术语。

###### 1、常用术语 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70]  
结点的度：子结点的个数。例如结点1中有3个子结点，结点1的度是3。

树的度：树的度等于所有结点度中度最高的值。结点最高的度为3，树的度为3。

叶子结点：度为0的结点，即没有子结点的结点。例如：上图中3，5，6，7，9，10。

分支结点：除了叶子结点以外的结点，即度不为0的结点。例如：上面树的分支结点为1，2，4，8。

层次： 图中已经表出来了，根为第一层，根的孩子为第二层，依此类推，若某结点在第i层，则其孩子结点在第 i+1层。0层、1层、2层、3层。

树的深度：树中结点的最大层，此树的深度为4（4层）。

总结点 = 所有度结点的和+1（父结点）

###### 2、树的具体类型和性质 ######

我们先来介绍一下二叉树，因为二叉树是一种特殊的树，其具有如下特点：

（1）、每个结点最多有两颗子树，结点的度最大为2。
    
    （2）、左子树和右子树是有顺序的，次序不能颠倒。
    
    （3）、即使某结点只有一个子树，也要区分左右子树。

二叉树常见的树结构包括：二叉查找树（二叉排序树）、平衡二叉树（AVL树）、完全二叉树、满二叉树。各种二叉树又有不同的性质，详情如下。

###### （1）、二叉查找树（二叉搜索树、二叉排序树） ######

![在这里插入图片描述][20190115150923148.jpg]

二叉查找树是一种动态查找表，具有这些性质：

1）、若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值； 
    2）、若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值； 
    3）、其他的左右子树也分别为二叉查找树； 
    4）、二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。

说明：二叉排序树的中序遍历为递增的序列。

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

![在这里插入图片描述][20190115150727947.jpg]

含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵树，那就是平衡二叉树，具有以下性质：

1）、要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1； 
    2）、其左右子树也都是平衡二叉树； 
    3）、二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。

说明：平衡二叉树首先是一棵二叉排序树，其次根节点左右子树的深度之差的绝对值不超过1。

###### （3）、满二叉树 ######

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。关键在于树的平衡。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70 1]

满二叉树特点：

1）、叶子只能出现在最下一层。
    2）、非叶子结点度一定是2.
    3）、在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

说明：没有度为1的节点

###### （4）、完全二叉树 ######

对一棵具有n个结点的二叉树按层序排号，如果编号为 i 的结点与同样深度的满二叉树编号为 i 结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70 2]![在这里插入图片描述][2019011521383745.png]

完全二叉树的特点：

1）、叶子结点只能出现在最下一层
    2）、最下层叶子结点一定集中在左子树上连续位置。
    3）、倒数第二层，如有叶子节点，一定出现在右子树上连续位置。
    4）、同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。

说明：所有的叶结点都出现在第k层或k-l层（层次最大的两层）、对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

###### （5）、红黑树 ######

![在这里插入图片描述][20190115214817574.jpg]  
红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：

1）、根节点只能是黑色； 
    2）、红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色； 
    3）、其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间； 
    4）、在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。

###### 2、B树 ######

B树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B树（当m等于2时，就是一棵2阶B树），下图为一棵四阶B树。

![在这里插入图片描述][20190115220849692.png]

一棵m阶B树是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

1）、树中每个节点至多有m棵子树； 
    2）、若根节点不是叶子节点，则至少有2棵子树； 
    3）、除根节点之外的所有非终端节点至少有棵子树； 
    4）、每个节点中的信息结构为（A0,K1,A1,K2......Kn,An），其中n表示关键字个数，Ki为关键字，Ai为指针； 
    5）、所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。

下面是往B树中依次插入

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

的演示动画：  
![在这里插入图片描述][20190115220904300.gif]

###### 3、B+树 ######

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

B+数是B树的一种变形，它与B树的差别在于：

1）、有n棵子树的节点含有n个关键字； 
    2）、非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。 
    3）、树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

下图是B+树的插入动画：  
![在这里插入图片描述][20190115220406736.gif]

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

###### 4、小节 ######

B+ 树的优点：

（1）、由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。  
（2）、B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

（3）、但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B 树和B+树的区别图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70 4]

再次说明，B树的中间节点包含数据信息，B+树在内部节点上不包含数据信息，数据信息全在叶子节点。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70]: /images/20220326/3288c46fa2e04e1789d07349f3dd09c0.png
[20190115150923148.jpg]: /images/20220326/38be9f0ec14a41e2b34662129daba687.png
[20190115150727947.jpg]: /images/20220326/c09c20f82d3e4efebfe0d46e0e40334d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70 1]: /images/20220326/80a80dc769f042f5b178d05fea0d88b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190115213820685.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU=,size_16,color_FFFFFF,t_70
[2019011521383745.png]: /images/20220326/6e0eac5db3fc487285fceeb457ef51a0.png
[20190115214817574.jpg]: /images/20220326/642fa239fdf14e00ba6ec953ce8ca84d.png
[20190115220849692.png]: /images/20220326/4db947f9a40b4166b57421685a4a5645.png
[20190115220904300.gif]: /images/20220326/42014877ad6f4d31a79421aad8afb9fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70 3]: /images/20220326/b4be91f48a0445de980dd1dd369f7290.png
[20190115220406736.gif]: /images/20220326/111a4e77296845e9a3255338e5709fcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p4ZDE0MzU1MTM3NzU_size_16_color_FFFFFF_t_70 4]: /images/20220326/8e737c8d405d49cbb74be78e81e68f96.png