一、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指向关键字属于(K[i-1], K)的子树
二、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.重复上述的步骤直到哈夫曼树构造完成
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
