数据结构——B树、B+树、哈夫曼树

一、B树概念

B树的出现是为了弥合不同的存储级别之间的访问速度上的巨大差异，实现高效的 I/O。平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构。
B树常用于磁盘当中，红黑树用于内存当中，由于磁盘的读取速度很慢，红黑树是二叉树，即使查找速率很快，但是会执行很多的I/O操作，必然会拖延速度
B树在磁盘中的操作优，红黑树在内存中优。

1.B树的构造

在B树的构造前需要明白M阶B树的概念。
M阶B树：是指可以分出M个叉，拥有M-1个节点。
其中的每一个节点都包括key和value key：对每一个文件的标号 。 value：页

B树的构造和2-3-4树的构造方式相似，从底开始构造，一层一层的向上送。
1.构造5阶B树的过程，以下列数据为参考构造5阶B树。

2.将每一个节点按照顺序排列直到4个节点为一组的情况。

3.当一组的节点超过4个的情况下，将中间的节点提到上一层，并且原本一组分成两份。

4.重复进行上述操作，得到最后的结果。

2 .B树的特点

节点的子树数量：B树的每个节点可以有多个子树，具体数量由树的阶数决定。对于一棵m阶B树，每个节点最多可以有m个子树
关键字数量：每个非根节点包含的关键字数量满足：⌈m/2⌉ - 1 <= j <= m - 1。根节点至少有2个子女
子树数量：除根节点外的所有节点（不包括叶子节点）的度数正好是关键字总数加1，子树数量k满足：⌈m/2⌉ <= k <= m
叶子节点：所有的叶子节点都位于同一层
节点结构：非叶子节点的指针P[1], P[2], …, P[M]，其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树

二、B+树概念

1、B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。
2、B+树的非叶子节点具有索引值，在内存相同的情况下，能够存放更多的key，树的高度就会越低。
3、B+树的所有叶子节点都相连、有序链表、对整棵树的遍历只需要线性遍历一遍叶子节点。
4、B+树常用于数据库底层。

1.B+树构造

B+树的构造类似于B树的构造但是在 **3.当一组的节点超过4个的情况下，将中间的节点提到上一层，并且原本一组分成两份。**时，并不将其value指提到上面，只需要将key值放到上一层，并且在叶子节点的那一层中创建有序链表

2.B+树的特点

1、所有数据都存储在叶子节点：B+树的非叶子节点仅存储索引信息，而所有实际数据都存储在叶子节点中。这使得B+树的查询效率更加稳定，因为每次查询都必须从根节点走到叶子节点，路径长度相同
2、叶子节点形成有序链表：B+树的叶子节点通过指针连接，形成一个有序链表。这使得范围查询和排序操作更加高效，只需遍历叶子节点即可
3、磁盘I/O次数更少：由于非叶子节点不存储数据，B+树的每个节点可以存储更多的关键字，从而减少了磁盘I/O操作的次数
4、支持高效的范围查询：B+树的叶子节点形成有序链表，支持高效的范围查询。只需在叶子节点上遍历即可，不需要像B树那样进行中序遍历
5、更适合文件索引和数据库索引：B+树的结构特点使其在文件索引和数据库索引中具有优势。它能够有效减少查找时间，提高存储的空间局部性，从而减少I/O操作
6、查询性能稳定：由于所有数据都存储在叶子节点，B+树的查询性能更加稳定。每次查询都必须从根节点走到叶子节点，路径长度相同
处理随机I/O和大跨度插入时性能下降：B+树在处理随机I/O和大跨度插入时可能会导致性能下降。随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离得很远。

三、B树和B+树的区别

1.B树常用于磁盘当中读取数据的操作，B+树用于数据库的底层。
2.B树非叶子节点包括key和value，但是B+树只包括key值，因此相同内存下B+树的高度会比B树低
3.B+树叶子节点间构成了有序的链表，非常方便进行区间查找操作，因此用于数据库
4.B+扫库、表能力更强。
5.B+的磁盘读写能力更强。
6.B+Tree 的节点上是不保存数据的，那么它保存的关键字就更多，这样一次 IO 操作，加载的关键字就更多，所以它的磁盘读写能力更强。
7.B+的叶子节点天然就是顺序存放的 。 B+树叶子节点是顺序排列的，并且相邻节点具有顺序引用的关系
8.B+ 的查询效率更加稳定。

四、哈夫曼树

1.哈夫曼树的基本概念

路径：从树中的一个节点到叶子节点的路径。
树的路径长度：从根节点到每一个叶子节点的路径长度之和
权：该节点的值
节点的带权路径长度：从根节点到该节点的路径长度与节点的权值的乘积
树的带权路径长度
哈夫曼树：*树的带权路径长度最小的树（WPL）

2.哈夫曼树的构建

1.提供一组数，将该组数按大小顺序排序完成

2.从小到大，依次取两个数据，获得两个数之和，赋值给父节点

3.将两个值的和重新和原来的数据排序

4.重复上述的步骤直到哈夫曼树构造完成