8分钟，复习一遍B树，B+树！
简单介绍
什么是B树，B+树？
B 树
B 树(B- 树) 指的是 Balance Tree，又名平衡多路（即不止两个子树）查找树，并且所有叶子节点位于同一层。
B+ 树
B+ 树基于B 树和叶子节点顺序访问指针进行实现，具有 B 树的平衡性，并且通过顺序访问指针来提高区间查询的性能。通常用于数据库和操作系统的文件系统中。
B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
B树，B+树的使用场景
文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：
Windows：HPFS文件系统Mac：HFS，HFS+文件系统Linux：ResiserFS，XFS，Ext3FS，JFS文件系统- 数据库：
ORACLE，MYSQL，SQLSERVER等中 - 数据库：
ORACLE，MYSQL，SQLSERVER等中
具体一点
-
B树
MongoDB数据库使用，单次查询平均快于MySQL(但侧面来看MySQL至少平均查询耗时差不多)ORACLE数据库
-
B+树
-
MySQL数据库普遍使用B+树来实现索引结构MyISAM索引实现InnoDB索引实现
-
这里注意了，
Redis用的是skiplist(跳表) 作为底层，而没有使用平衡树这一结构
磁盘概述
现在我们知道了B，B+树主要用在文件系统和数据库了。本篇我们将简单的介绍磁盘这个存储结构，为接下来的学习做铺垫。
磁盘结构示意图
-
整体结构
-
横切面
我们都知道，计算机的存储管理是分层的，各层次之间的速度差距比较大，尤其是辅存（磁盘）和主存之间的速度。我们也知道磁盘访问比较慢，为什么会慢呢？
-
关于访存
CPU访问磁盘时，磁盘主要干了这些事：
- 寻道：磁头摆一摆，找到对应的柱面
- 定位：盘面转一转，磁头定位到指定扇区
在访存的两个步骤中，因为是机械操作比不上主存的电信号传播，所以自然就慢了不少，磁盘访问慢了，访问效率自然就跟不上了。
那么能不能再不改变这种机械运动的情况下提升访存效率呢？
能。使用索引就可以。
-
什么是索引？
索引就好比是书的目录，比如当我们查看一本字典的时候，目录就相当于我们的对照表。索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。
所以这就要求我们建立一个好的索引来帮助我们提升访存效率。
磁盘读写原理
-
局部性原理
在一小段时间里，程序执行所访问的存储空间局限于某个内存区域。(在这一小段时间内程序只会用这一部分内存的这一小撮数据)
-
磁盘预读
在有了局部性原理之后。这程序执行依次要一个数据，现在我们知道它要的数据基本都是一堆一堆的凑在一起的，那我就可以在它要之前我这个磁盘先读着我这个扇区下面的内容，不管程序是否需要。这个就是磁盘预读，预读的长度一般为页（page）的整数倍。（页是数据存储的单位。页面从主存储器加载到处理器中。页由单元块或块组组成。）
在了解了磁盘以后，我们知道问题是如何利用索引来提高访存速度。而B，B+树就是为了解决这个问题而存在的。
为什么使用B，B+树？
传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等。这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了。（这些树的高度比较高）
原因当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右。速度相差了近 5 个数量级，磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。
那么我们如何提高程序性能？减少磁盘 IO 次数，像 AVL 树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘。
平衡二叉树是通过旋转来保持平衡的，而旋转是对整棵树的操作，若部分加载到内存中则无法完成旋转操作。 其次平衡二叉树的高度相对较大为 log n（底数为2），这样逻辑上很近的节点实际可能非常远，无法很好的利用磁盘预读（局部性原理） 。
在最坏的情况下，一次IO就只能获得一个结点的值，所以在最坏的情况下，不管是红黑树还是AVL树、B树、B+树，他们对应的磁盘操作是树的高度。而B树和B+树的高度是低的，适应数据库和文件系统的。
所以 AVL 树，红黑树这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。
更多细节将在 “剖析 B树，B+树” 章节解释
B树，B+树的特征
本篇为对B树和B+树的特征列举, 详细的部分在下一章对比中给出
B 树的特征
-
一个m阶的B树有如下几个特征：
- 若根结点不是终端结点，则至少有2棵子树。
- 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
- 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
- 所有的叶子结点都位于同一层。
- 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
-
B 树(3阶)示例:
B+ 树的特征
-
一棵m阶B+树具有如下几个特征：
- 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
- 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
-
B+ 树(3阶)示例：
解释：
B+ 树始终要保持最大元素在根节点当中。
B+ 树的叶子节点包含了全量元素信息。并且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。
无论是B树还是B+树，最底层呈现的都是有序序列。
AVL树 vs B树 vs B+树
关于平衡二叉树的内容可以看我的另一篇博客：juejin.cn/post/713638…
AVL 树（左），B 树（右）
-
B树的节点和AVL树的节点结构不同
平衡二叉树的节点，每个最多有一个数据和最多两个子树。
B树的节点，每个节点可以有不止一个数据，同时可以拥有的子树数量是阶数决定的。
-
B树的查找效率更高
B树的每个节点可以表示的信息更多，因此整个树更加“矮胖”，这在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘 IO 的次数，从而提升查找速度。
B树既然这么多好处了，那么B+树呢？
B 树（上），B+树（下）
-
B+树的磁盘读写代价更低(节点结构不同决定)
B+树的非叶子节点不存储数据，所以其内部结点相对B树更小，如果把所有同一非叶子结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。相对来说IO读写次数也就降低了，查找速度更快了。
-
B+树查询效率更稳定
B+树内非叶子节点不存储数据，而是只是叶子结点关键字的索引，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。 所以B+树中任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，导致每一个数据的查询效率相当，而对于B树来说，因为每个结点都存有具体的数据，因此其查询速度不稳定，可能很快也可能很慢。
举个例子：
我们查询 9 这个元素，从上图可以看出，key 为 9 的节点就在第一层，B树只需要一次磁盘 IO 即可完成查找。所以说B树的查询最好时间复杂度是 O(1)。由于B+树所有的 data 域都在根节点，所以查询 key 为 9的节点必须从根节点索引到叶节点，时间复杂度固定为 O(log n)。
-
B+树便于范围查询
B树在提高了IO性能的同时，并没有解决元素遍历效率低下的问题。为了解决这个问题，B+树应运而生。
B+树只需要遍历叶子结点就可以实现整棵树的遍历（B+树叶子结点维护有序链表。在数据库中基于范围的查找也是非常频繁的，因此
MySQL的Innodb引擎就使用了B+树作为其索引的数据结构
深入剖析 B树，B+树
卫星数据
什么是卫星数据？
卫星数据指索引元素所指向的数据记录，
比如数据库中的某一行。
在B树中，无论非叶子结点还是叶子结点都带有卫星数据；
而在B+树中只有叶子结点带有卫星数据，其余非终端结点仅仅是索引，没有任何数据关联。
拿MySQL中的聚簇索引和非聚簇索引举例
在MySQL数据库的聚簇索引中，叶子结点直接包含卫星数据；在非聚簇索引中，叶子结点带有指向卫星数据的指针。
B 树
23树，234树
在我的文章：8分钟，复习一遍红黑树！中，我介绍了红黑树的前身——234树，而实际上234树就是4阶B树，23树就是3阶B树！
这样一来，本章的目的之一 “对B树的剖析” 就不是难事了。
- 234树（4阶B树）：是一种多叉树，它的每个节点最多有3个数据项和4个子节点。
- 23树（3阶B树）：是一种多叉树，它的每个节点最多有2个数据项和3个子节点。
所以，B树的插入以及删除等操作完全就可以用234树，23树来解释。
下一个篇章我们将介绍B树的常见操作。
B 树的操作
插入
关于234树的插入操作在8分钟，复习一遍红黑树！中已经详细说明，这里就不展开了。
查找
假设每个节点有 n 个 key值，被分割为 n+1 个区间，注意，B树的 key 和 data 实际是聚合在一起的，因为B树的所有节点都是卫星数据！
一般而言，根节点都在内存中，B树以每个节点为一次磁盘 IO。
比如上图中，若搜索 key 为 3 节点的 data，首先在根节点进行二分查找（因为 keys 有序，二分最快），判断 key 3 小于 key 5，所以定位到最左侧的节点，此时进行一次磁盘 IO，将该节点从磁盘读入内存，接着继续进行上述过程，直到找到该 key 为止。
查找伪代码：
Node* BTreeSearch(Root *root, Key key)
{
Node* node;
if(root == NULL)
return NULL;
node = BinarySearch(root,key); // 在根节点进行二分查找，进行当前节点定位
if(node->key == key)
{// 找到key了
return node;
}else{
root = ReadDisk(node->next); // 进行一次磁盘IO，将下一个节点读入到内存
BTreeSearch(root, key); // 递归寻找
}
}
B 树如何迎合磁盘
本篇我们从“迎合”磁盘的角度来看看B树的设计。
索引的效率依赖于磁盘 IO 的次数，快速索引需要有效的减少磁盘 IO 次数。
索引的原理？B树是如何快速索引的？
索引的原理其实是不断的缩小查找范围，就如我们平时用字典查单词一样，先找首字母缩小范围，再第二个字母等等。
平衡二叉树是每次将范围分割为两个区间。为了更快，B树每次将范围分割为多个区间，区间越多，定位数据越快越精确。那么如果节点为区间范围，每个节点就较大了。
实际设计中，我们把一个节点设为一个页，直接申请页大小的空间。（磁盘存储单位是按 block 分的，一般为 512 Byte。磁盘 IO 一次读取若干个 block，我们称为一页，具体大小和操作系统有关，一般为 4 k，8 k或 16 k）
计算机内存分配是按页对齐的，这样就实现了一个节点只需要一次 IO。
上图是一棵简化的B树，多叉的好处非常明显，有效的降低了B树的高度。现在的高度为底数很大的 log n，底数大小与节点的子节点数目有关，一般一棵B树的高度在 3 层左右。
层数低，每个节点区确定的范围更精确，范围缩小的速度越快（比二叉树深层次的搜索肯定快很多）。
上面说了一个节点需要进行一次 IO，那么总 IO 的次数就缩减为了 log n 次。
B树的每个节点是 n 个有序的序列(a_1,a_2,a_3…a_n)，并将该节点的子节点分割成 n+1 个区间来进行索引(X_1< a_1, a_2 < X_2 < a_3, … , a_{n+1} < X_n < a_n, X_{n+1} > a_n)。
解释：B树的每个节点，都是存多个值的，不像二叉树那样，一个节点就一个值，B树把每个节点都给了一点的范围区间，区间更多的情况下，搜索也就更快了，比如：有1-100个数，二叉树一次只能分两个范围，0-50和51-100，而B树，分成4个范围 1-25， 25-50，51-75，76-100 一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的
所以，B树就是一个很好的索引结构，因为它有效的减少了磁盘 IO 次数！
B 树代码实现
本篇代码引用自：
public class BTree<Key extends Comparable<Key>, Value>
{
// max children per B-tree node = M-1
// (must be even and greater than 2)
private static final int M = 4;
private Node root; // root of the B-tree
private int height; // height of the B-tree
private int n; // number of key-value pairs in the B-tree
// helper B-tree node data type
private static final class Node
{
private int m; // number of children
private Entry[] children = new Entry[M]; // the array of children
// create a node with k children
private Node(int k)
{
m = k;
}
}
// internal nodes: only use key and next
// external nodes: only use key and value
private static class Entry
{
private Comparable key;
private Object val;
private Node next; // helper field to iterate over array entries
public Entry(Comparable key, Object val, Node next)
{
this.key = key;
this.val = val;
this.next = next;
}
}
/**
* Initializes an empty B-tree.
*/
public BTree()
{
root = new Node(0);
}
/**
* Returns true if this symbol table is empty.
* @return {@code true} if this symbol table is empty; {@code false} otherwise
*/
public boolean isEmpty()
{
return size() == 0;
}
/**
* Returns the number of key-value pairs in this symbol table.
* @return the number of key-value pairs in this symbol table
*/
public int size()
{
return n;
}
/**
* Returns the height of this B-tree (for debugging).
*
* @return the height of this B-tree
*/
public int height()
{
return height;
}
/**
* Returns the value associated with the given key.
*
* @param key the key
* @return the value associated with the given key if the key is in the symbol table
* and {@code null} if the key is not in the symbol table
* @throws NullPointerException if {@code key} is {@code null}
*/
public Value get(Key key)
{
if (key == null)
{
throw new NullPointerException("key must not be null");
}
return search(root, key, height);
}
@SuppressWarnings("unchecked")
private Value search(Node x, Key key, int ht)
{
Entry[] children = x.children;
// external node到最底层叶子结点，遍历
if (ht == 0)
{
for (int j = 0; j < x.m; j++)
{
if (eq(key, children[j].key))
{
return (Value) children[j].val;
}
}
}
// internal node递归查找next地址
else
{
for (int j = 0; j < x.m; j++)
{
if (j+1 == x.m || less(key, children[j+1].key))
{
return search(children[j].next, key, ht-1);
}
}
}
return null;
}
/**
* Inserts the key-value pair into the symbol table, overwriting the old value
* with the new value if the key is already in the symbol table.
* If the value is {@code null}, this effectively deletes the key from the symbol table.
*
* @param key the key
* @param val the value
* @throws NullPointerException if {@code key} is {@code null}
*/
public void put(Key key, Value val)
{
if (key == null)
{
throw new NullPointerException("key must not be null");
}
Node u = insert(root, key, val, height); //分裂后生成的右结点
n++;
if (u == null)
{
return;
}
// need to split root重组root
Node t = new Node(2);
t.children[0] = new Entry(root.children[0].key, null, root);
t.children[1] = new Entry(u.children[0].key, null, u);
root = t;
height++;
}
private Node insert(Node h, Key key, Value val, int ht)
{
int j;
Entry t = new Entry(key, val, null);
// external node外部结点，也是叶子结点，在树的最底层，存的是内容value
if (ht == 0)
{
for (j = 0; j < h.m; j++)
{
if (less(key, h.children[j].key))
{
break;
}
}
}
// internal node内部结点，存的是next地址
else
{
for (j = 0; j < h.m; j++)
{
if ((j+1 == h.m) || less(key, h.children[j+1].key))
{
Node u = insert(h.children[j++].next, key, val, ht-1);
if (u == null)
{
return null;
}
t.key = u.children[0].key;
t.next = u;
break;
}
}
}
for (int i = h.m; i > j; i--)
{
h.children[i] = h.children[i-1];
}
h.children[j] = t;
h.m++;
if (h.m < M)
{
return null;
}
else
{ //分裂结点
return split(h);
}
}
// split node in half
private Node split(Node h)
{
Node t = new Node(M/2);
h.m = M/2;
for (int j = 0; j < M/2; j++)
{
t.children[j] = h.children[M/2+j];
}
return t;
}
/**
* Returns a string representation of this B-tree (for debugging).
*
* @return a string representation of this B-tree.
*/
public String toString()
{
return toString(root, height, "") + "\n";
}
private String toString(Node h, int ht, String indent)
{
StringBuilder s = new StringBuilder();
Entry[] children = h.children;
if (ht == 0)
{
for (int j = 0; j < h.m; j++)
{
s.append(indent + children[j].key + " " + children[j].val + "\n");
}
}
else
{
for (int j = 0; j < h.m; j++)
{
if (j > 0)
{
s.append(indent + "(" + children[j].key + ")\n");
}
s.append(toString(children[j].next, ht-1, indent + " "));
}
}
return s.toString();
}
// comparison functions - make Comparable instead of Key to avoid casts
private boolean less(Comparable k1, Comparable k2)
{
return k1.compareTo(k2) < 0;
}
private boolean eq(Comparable k1, Comparable k2)
{
return k1.compareTo(k2) == 0;
}
}
B+ 树
在了解完成B树以后我们就来讲讲看B+树
B+ 树的操作
查找
首先，Ｂ＋树的查找和Ｂ树一样，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。
结合我们的卫星数据的概念，我们再一次剖析一下B+树的查找
B+树的优势在于查找效率和稳定性
- B+ 树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页B+树可以容纳更多节点元素。在相同的数据量下，Ｂ+ 树更加“矮胖”，IO操作更少。
- B树的查找性能并不稳定（最好情况只查询根节点，最坏情况是查找叶子节点）。而B+树的每一次查找都是稳定的，每次都是根据索引查询到叶子。
单行查询
一般的查找和B树并没有太大区别，只是B+树要找到链表为止。
在 「AVL树 vs B树 vs B+树」一章中我们讲了B+树更便于范围查询，于是我们接着就来讲范围查询
范围查询
-
B树的范围查询
查询范围：[3, 9]
方式：利用平衡树中序遍历有序的性质。
自定向下，查找到范围下限 3
中序遍历到5
中序遍历到6
中序遍历到8
中序遍历到上限9，结束
-
B+ 树的范围查询
查询范围：[3, 9]
自定向下，查找到范围下限 3
通过链表指针，遍历到9
所以这里就能很清楚的理解为什么说B+树更加适合范围查询了。
B+ 树代码实现
本篇代码引用自: blog.csdn.net/nandao158/a…
public class CatalogBTree<Key extends Comparable<Key>, Value> {
//参数M 定义每个节点的链接数
private static final int M = 4;
private Node root;
//树的高度 最底层为0 表示外部节点 根具有最大高度，此高度是根之后的高度
private int height;
//键值对总数
private int n;
//节点数据结构定义
private static final class Node{
//值的数量
private int m;
private Entry[] children = new Entry[M];
private Node(int k){
m = k;
}
}
//节点内部每个数据项定义
private static class Entry{
private Comparable key;
private final Object val;
//下一个节点
private Node next;
public Entry(Comparable key, Object val, Node next){
this.key = key;
this.val = val;
this.next = next;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Entry [key=");
builder.append(key);
builder.append("]");
return builder.toString();
}
}
public CatalogBTree(){
root = new Node(0);
}
public int size(){
return n;
}
public boolean isEmpty(){
return size() == 0;
}
public int height(){
return height;
}
/**
* 查询接口
* @param key
* @return
*/
public Value get(Key key){
return search(root, key, height);
}
private Value search(Node x, Key key, int ht) {
Entry[] children = x.children;//首次进入，相当于根节点
//外部节点 这里使用顺序查找
//如果M很大 可以改成二分查找
if(ht == 0){//到了有数据的子节点（也可能是根节点，如果键值对小于M），此次查询数据。
for(int j=0; j<x.m; j++){
if(equal(key, x.children[j].key))//遍历查询
return (Value)children[j].val;
}
}
//内部节点 寻找下一个节点
else{
for(int j=0; j<x.m; j++){
//最后一个节点 或者 插入值小于某个孩子节点值
if(j+1==x.m || less(key, x.children[j+1].key))//定位数据在哪个节点下，然后继续递归查询
return search(x.children[j].next, key, ht-1);//去下一层继续查询
}
}
return null;
}
/**
* 新增数据接口
* @param key
* @param val
*/
public void put(Key key, Value val){
//插入后的节点，如果节点分裂，则返回分裂后产生的新节点
Node u = insert(root, key, val, height);
n++;//键值对总数加一
if(u == null) return;//根节点没有分裂 直接返回
//分裂根节点,已满节点进行分裂，将已满节点后M/2节点生成一个新节点，并将新节点的第一个元素指向父节点，此处是M>>1 = 2（因为M=4）
Node t = new Node(M>>1);
//旧根节点第一个孩子和新分裂节点第一个孩子 共同 组成新节点作为根
t.children[0] = new Entry(root.children[0].key, null, root);
t.children[1] = new Entry(u.children[0].key, null, u);
root = t;//新的根节点
height++;//节点高度加1
}
private Node insert(Node h, Key key, Value val, int ht) {
int j;
//新建待插入数据数据项
Entry t = new Entry(key, val, null);
if(ht == 0){//高度为零时，直接遍历
for(j=0; j<h.m; j++){ // 外部节点 找到带插入的节点位置j
if(less(key, h.children[j].key))
break;
}
}else{
//内部节点 找到合适的分支节点
for(j=0; j<h.m; j++){
if(j+1==h.m || less(key, h.children[j+1].key)){
Node u = insert(h.children[j++].next, key, val, ht-1);
if(u == null) return null;
t.key = u.children[0].key;
t.next = u;
break;
}
}
}
//j为带插入位置，将顺序数组j位置以后后移一位(从后往前处理) 将t插入
for(int i=h.m; i>j; i--){
h.children[i] = h.children[i-1];
}
System.out.println(j + t.toString());
h.children[j] = t;//此处插入成功
h.m++;//值的数量加一
if(h.m < M) return null;
//如果节点已满 则执行分类操作（从根节点开始）
else return split(h);
}
private Node split(Node h) {
//将已满节点h的后，一般M/2节点后的节点分裂到新节点并返回
Node t = new Node(M/2);
h.m = M / 2;
for(int j=0; j<M/2; j++){
t.children[j] = h.children[M/2+j];//把h节点中M/2节点后的节点分裂到新节点
h.children[M/2+j] = null;//把h节点中M/2节点后的节点设置为空，以尽快GC
}
return t;//返回新节点
}
/**
* 删除数据
* @param key
*/
public void remove(Key key){
remove(root, key, height);
}
private void remove(Node x, Key key, int ht){
Entry[] children = x.children;//首次进入，相当于根节点
//外部节点 这里使用顺序查找
//如果M很大 可以改成二分查找
if(ht == 0){//到了有数据的子节点（也可能是根节点，如果键值对小于M），此次查询数据。
for(int j=0; j<x.m; j++){
if(equal(key, x.children[j].key)){//遍历查询
children[j] = null;//删除此节点数据
x.m--;//值的数量减一
}
}
}
//内部节点 寻找下一个节点
else{
for(int j=0; j<x.m; j++){
//最后一个节点 或者 插入值小于某个孩子节点值
if(j+1==x.m || less(key, x.children[j+1].key))//定位数据在哪个节点下，然后继续递归查询
remove(x.children[j].next, key, ht-1);//去下一层继续查询
}
}
}
private boolean equal(Comparable k1, Comparable k2){
return k1.compareTo(k2)==0;
}
private boolean less(Comparable k1, Comparable k2){
return k1.compareTo(k2)<0;
}
public String toString() {
return toString(root, height, "") + "\n";
}
private String toString(Node h, int ht, String indent) {
StringBuilder s = new StringBuilder();
Entry[] children = h.children;//此数据相当于根节点
//外部节点
if (ht == 0) {
for (int j = 0; j < h.m; j++) {
s.append(indent + children[j].key + " " + children[j].val + "\n");
}
}
else {
for (int j = 0; j < h.m; j++) {
s.append(indent + "(" + children[j].key + ")\n");
s.append(toString(children[j].next, ht-1, indent + " "));
}
}
return s.toString();
}
}
功能测试
本篇代码引用自：
B 树
测试建树：
public class TestBTree {
@Test
public void testCreateTree(){
BTree<String, String> st = new BTree<String, String>();
st.put("www.cs.princeton.edu", "128.112.136.12");
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.128.15");
st.put("www.yale.edu", "130.132.143.21");
st.put("www.simpsons.com", "209.052.165.60");
st.put("www.apple.com", "17.112.152.32");
st.put("www.amazon.com", "207.171.182.16");
st.put("www.ebay.com", "66.135.192.87");
st.put("www.cnn.com", "64.236.16.20");
st.put("www.google.com", "216.239.41.99");
st.put("www.nytimes.com", "199.239.136.200");
st.put("www.microsoft.com", "207.126.99.140");
st.put("www.dell.com", "143.166.224.230");
st.put("www.slashdot.org", "66.35.250.151");
st.put("www.espn.com", "199.181.135.201");
st.put("www.weather.com", "63.111.66.11");
st.put("www.yahoo.com", "216.109.118.65");
System.out.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu"));
System.out.println("hardvardsucks.com: " + st.get("www.harvardsucks.com"));
System.out.println("simpsons.com: " + st.get("www.simpsons.com"));
System.out.println("apple.com: " + st.get("www.apple.com"));
System.out.println("ebay.com: " + st.get("www.ebay.com"));
System.out.println("dell.com: " + st.get("www.dell.com"));
System.out.println();
System.out.println("size: " + st.size());
System.out.println("height: " + st.height());
System.out.println(st);
System.out.println();
}
}
测试结果：
cs.princeton.edu: 128.112.136.12
hardvardsucks.com: null
simpsons.com: 209.052.165.60
apple.com: 17.112.152.32
ebay.com: 66.135.192.87
dell.com: 143.166.224.230
size: 17
height: 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.google.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpsons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
B+ 树
测试建树：
public class TestCatalogBTree {
@Test
public void testCreateTree(){
/**
* 添加的顺序不同，最后树的结构也不同
*/
CatalogBTree<Integer,String> bt = new CatalogBTree<>();
bt.put(5,"a");
bt.put(8,"b");
// bt.put(9,"c");
bt.put(10,"d");
bt.put(15,"e");
// bt.put(18,"f");
bt.put(20,"g");
bt.put(26,"h");
// bt.put(27,"i");
bt.put(28,"i");
bt.put(30,"j");
// bt.put(33,"k");
bt.put(35,"l");
bt.put(38,"m");
// bt.put(50,"n");
bt.put(56,"o");
bt.put(60,"p");
// bt.put(63,"q");
bt.put(65,"r");
bt.put(73,"s");
// bt.put(79,"t");
bt.put(80,"u");
bt.put(85,"v");
// bt.put(88,"w");
bt.put(90,"x");
bt.put(96,"y");
bt.put(99,"z");
/**
* 插入第三个元素
*/
bt.put(9,"c");
bt.put(18,"f");
bt.put(27,"i");
bt.put(33,"k");
bt.put(50,"n");
bt.put(63,"q");
bt.put(79,"t");
bt.put(88,"w");
System.out.println("高度："+bt.height());
System.out.println("查询："+bt.get(9));
System.out.println( bt.toString());
}
}
测试结果：
0Entry [key=5]
1Entry [key=8]
2Entry [key=10]
3Entry [key=15]
2Entry [key=20]
3Entry [key=26]
2Entry [key=20]
2Entry [key=28]
3Entry [key=30]
3Entry [key=28]
2Entry [key=35]
3Entry [key=38]
2Entry [key=35]
2Entry [key=56]
3Entry [key=60]
3Entry [key=56]
2Entry [key=35]
2Entry [key=65]
3Entry [key=73]
2Entry [key=65]
2Entry [key=80]
3Entry [key=85]
3Entry [key=80]
3Entry [key=65]
2Entry [key=90]
3Entry [key=96]
2Entry [key=90]
2Entry [key=99]
2Entry [key=9]
2Entry [key=18]
2Entry [key=27]
2Entry [key=33]
2Entry [key=50]
2Entry [key=63]
2Entry [key=79]
2Entry [key=88]
高度：3
查询：c
(5)
(5)
(5)
5 a
8 b
9 c
(10)
10 d
15 e
18 f
(20)
(20)
20 g
26 h
27 i
(28)
28 i
30 j
33 k
(35)
(35)
(35)
35 l
38 m
50 n
(56)
56 o
60 p
63 q
(65)
(65)
65 r
73 s
79 t
(80)
80 u
85 v
88 w
(90)
90 x
96 y
99 z
小结
不得不说，B树以及B+树的内容还是挺多的，写这篇文章也花了我挺多精力和时间的。不过看完这篇文章以后，面对面试官 ”说说看B或B+树吧“ 的问题，应该是有得一聊了。
本篇代码已同步上传至我的开源仓库：github.com/pixel-revol…
本文参考：
- zhuanlan.zhihu.com/p/54102723
- juejin.cn/post/684490…
- mp.weixin.qq.com/s/jUTmb4FHI…
- www.jianshu.com/p/ace3cd652…
- blog.csdn.net/qq_21989927…
- www.jianshu.com/p/e3506cee4…
- blog.csdn.net/u011919863/…
- blog.csdn.net/wwh57886781…
- developer.aliyun.com/article/748…
- juejin.cn/post/692631…
- blog.csdn.net/nandao158/a…