本文共 24331 字，大约阅读时间需要 81 分钟。
简介
下面是写的b+树的java版本的代码，BPlusTree为对外开放b+树，BPlusNode为非叶子节点数据结构，LeafNode为叶子节点数据数据结构，Node为叶子节点和非叶子节点公用部分。
结合网上的图文教程然后来看这个代码会理解的比较快。
代码的注释已经很全了，就不做说明了。
源码
package com.smart.leetcode.tree.mybplustree;import java.util.LinkedList;import java.util.List;/** * 实现b+树 * * @param 值的类型 * @param 索引的类型，必须继承comparable */public class BPlusTree > { public long sum = 0; /** * b+树的阶数 */ private int bTreeOrder; /** * b+树非叶子节点拥有的最大节点数量 */ private int maxNumber; private Node root; public BPlusTree() { this(3); } public BPlusTree(int bTreeOrder) { this.bTreeOrder = bTreeOrder; this.maxNumber = bTreeOrder + 1; this.root = new LeafNode<>(); } public T find(V key) { return this.root.find(key); } List findByPre(String key) { return this.root.findByPre(key); } List findByRange(V start, V end) { return this.root.findByRange(start, end); } T delete(V key) { return this.root.delete(key, this); } public void insert(V key, T value) { if (key == null) { return; } Node t = this.root.insert(key, value); if (t != null) { this.root = t; } } abstract class Node > { /** * 父节点 */ protected Node parent; /** * 子节点 */ protected Node [] children; /** * 子节点数量 */ protected int num; /** * 索引，索引下面挂小于等于索引的值 */ protected Object[] keys; public Node() { this.keys = new Object[maxNumber]; this.children = new Node[maxNumber]; this.num = 0; this.parent = null; } /** * 查找 */ abstract T find(V key); /** * 根据前缀查询 */ abstract List findByPre(String key); /** * 范围查询 */ abstract List findByRange(V start, V end); /** * 插入 */ abstract Node insert(V key, T value); /** * 删除 */ abstract T delete(V key, BPlusTree bPlusTree); /** * 更新父节点 */ abstract void updateRemove(BPlusTree bPlusTree); } class BPlusNode > extends Node { @Override T find(V key) { sum++; int i = 0; while (i < this.num) { //找到第一个大于等于自身的值，要找的值就在这个下面 if (key.compareTo((V) (V) this.keys[i]) <= 0) { break; } i++; } //如果比最大值还要大，代表没有找到 if (this.num == i) { return null; } return children[i].find(key); } @Override T delete(V key, BPlusTree bPlusTree) { int i = 0; while (i < this.num) { //找到第一个大于等于自身的值，要找的值就在这个下面 if (key.compareTo((V) (V) this.keys[i]) <= 0) { break; } i++; } //如果比最大值还要大，代表没有找到 if (this.num == i) { return null; } return children[i].delete(key, bPlusTree); } /** * 叶子节点删除做的更新处理 */ @Override void updateRemove(BPlusTree bPlusTree) { if (this.parent == null) { //如果是根节点并且子节点数大于等于2，则直接返回 if (this.num >= 2) { return; } //如果当前只有一个叶子节点了，就把这个叶子节点作为跟节点 bPlusTree.root = (Node) this.children[0]; bPlusTree.root.parent = null; return; } //找到当前节点在父节点中的位置 int cur = 0; Node left = null, right = null; for (int i = 0; i < this.parent.num; i++) { if (this.parent.children[i] == this) { cur = i; if (i > 0) { left = this.parent.children[i - 1]; } if (i < (this.parent.num - 1)) { right = this.parent.children[i + 1]; } break; } } //如果前节点子节点数大于m/2并且大于2，则从其处借补 if (left != null && left.num > bPlusTree.bTreeOrder / 2 && left.num > 2) { //借最后一个值 Node data = left.children[left.num - 1]; Object key = left.keys[left.num - 1]; //前面的值少一个 left.children[left.num - 1] = null; left.keys[left.num - 1] = null; left.num--; //当前所有的值往后挪一个 for (int i = this.num; i >= 0; i--) { this.children[i] = this.children[i - 1]; this.keys[i] = this.keys[i - 1]; } //保存借补的值 this.num++; this.children[0] = data; this.keys[0] = key; //上一个节点的最大值做调整 this.parent.keys[cur - 1] = left.keys[left.num - 1]; return; } //如果后节点子节点数大于m/2并且大于2，则从其处借补 if (right != null && right.num > bPlusTree.bTreeOrder / 2 && right.num > 2) { //获取后面的第一个节点 Node data = right.children[0]; Object key = right.keys[0]; this.num++; this.children[this.num - 1] = data; this.keys[this.num - 1] = key; for (int i = 0; i < (right.num - 1); i++) { right.children[i] = right.children[i + 1]; } right.num--; this.parent.keys[cur] = key; return; } //同前面节点合并 if (left != null && (left.num <= bPlusTree.bTreeOrder / 2 || left.num <= 2)) { //把当前值全部放到前面的节点中去 for (int i = 0; i < this.num; i++) { left.num++; left.children[left.num - 1] = children[i]; left.keys[left.num - 1] = keys[i]; } //删除父节点中的当前节点，特别注意，这里前节点的最大值就是当前节点的最大值了 parent.keys[cur - 1] = parent.keys[cur]; for (int i = cur; i < (parent.num - 1); i++) { parent.children[i] = parent.children[i + 1]; parent.keys[i] = parent.keys[i + 1]; } this.parent.num--; //如果父节点不合符合并要求了，则直接返回 //1.父节点存在父节点的情况，节点数大于m/2 //2.父节点是根节点的情况，节点数大于等于2 if ((this.parent.parent != null && (parent.num >= bPlusTree.bTreeOrder / 2 && parent.num >= 2)) || (parent.parent == null && parent.num >= 2)) { return; } parent.updateRemove(bPlusTree); return; } //同后面的节点合并 if (right != null && (right.num <= bPlusTree.bTreeOrder / 2 || right.num <= 2)) { //把后面节点的值全部放到当前节点 for (int i = 0; i < right.num; i++) { this.num++; this.children[this.num - 1] = right.children[i]; this.keys[this.num - 1] = right.keys[i]; } //删除父节点中的下一个节点，注意当前节点的最大值就是后面一个节点的最大值 this.parent.keys[cur] = this.parent.keys[cur + 1]; for (int i = (cur + 1); i <= parent.num; i++) { parent.children[i] = parent.children[i + 1]; parent.keys[i] = parent.keys[i + 1]; } this.parent.num--; if ((this.parent.parent != null && (parent.num >= bPlusTree.bTreeOrder / 2 && parent.num >= 2)) || (parent.parent == null && parent.num >= 2)) { return; } parent.updateRemove(bPlusTree); } } @Override List findByPre(String key) { int i = 0; while (i < this.num) { if (key.compareTo(this.keys[i].toString()) <= 0) { break; } i++; } //如果比最大值还要大，代表没有找到 if (this.num == i) { return null; } return children[i].findByPre(key); } @Override List findByRange(V start, V end) { int i = 0; while (i < this.num) { if (start.compareTo((V) this.keys[i]) <= 0) { break; } i++; } if (this.num == i) { return null; } return children[i].findByRange(start, end); } @Override Node insert(V key, T value) { int i = 0; while (i < this.num) { if (key.compareTo((V) this.keys[i]) < 0) { break; } i++; } //比最大值还大的先挂在最大值下面，后期再处理 if (key.compareTo((V) this.keys[this.num - 1]) >= 0) { i--; } return this.children[i].insert(key, value); } /** * * @param node1 当前节点 * @param node2 新增的节点 * @param key 原来节点在父类中的索引，如果为null，表示父节点是新增了，原来不存在 * @return 父节点，如果为空则不是父节点 */ Node insertNode(Node node1, Node node2, V key) { V oldKey = this.num > 0 ? (V) this.keys[this.num - 1] : null; //如果原有key为null,说明这个节点原来是不存在的，直接放入两个节点即可 if (key == null || this.num == 0) { this.keys[0] = node1.keys[node1.num - 1]; this.keys[1] = node2.keys[node2.num - 1]; this.children[0] = node1; this.children[1] = node2; this.num += 2; return this; } int i = 0; while (key.compareTo((V) this.keys[i]) != 0) { i++; } //左边节点的最大值需要做调整，后面节点的最大值需要插入 this.keys[i] = node1.keys[node1.num - 1]; this.children[i] = node1; //构造新的父节点 Object[] tempKeys = new Object[maxNumber]; Node [] tempChildren = (Node []) new Node[maxNumber]; System.arraycopy(this.keys, 0, tempKeys, 0, i + 1); System.arraycopy(this.children, 0, tempChildren, 0, i + 1); System.arraycopy(this.keys, i + 1, tempKeys, i + 2, this.num - i - 1); System.arraycopy(this.children, i + 1, tempChildren, i + 2, this.num - i - 1); tempKeys[i + 1] = (V) node2.keys[node2.num - 1]; tempChildren[i + 1] = node2; this.num++; //判断是否需要拆分 //如果不需要拆分，把数组复制回去，直接返回 if (this.num <= bTreeOrder) { System.arraycopy(tempKeys, 0, this.keys, 0, this.num); System.arraycopy(tempChildren, 0, this.children, 0, this.num); return null; } //如果需要拆分，从中间拆开 int mid = this.num / 2; //新建非叶子节点，作为拆分的右半部分 BPlusNode tempNode = new BPlusNode<>(); tempNode.num = this.num - mid; tempNode.parent = this.parent; if (this.parent == null) { BPlusNode tempBPlusNode = new BPlusNode<>(); tempNode.parent = tempBPlusNode; this.parent = tempBPlusNode; oldKey = null; } System.arraycopy(tempKeys, mid, tempNode.keys, 0, tempNode.num); System.arraycopy(tempChildren, mid, tempNode.children, 0, tempNode.num); for (int j = 0; j < tempNode.num; j++) { tempNode.children[j].parent = tempNode; } this.num = mid; this.keys = new Object[maxNumber]; this.children = new Node[maxNumber]; System.arraycopy(tempKeys, 0, this.keys, 0, mid); System.arraycopy(tempChildren, 0, this.children, 0, mid); //拆分成功后，需要把心生产的节点插入父节点 BPlusNode parentNode = (BPlusNode ) this.parent; return parentNode.insertNode(this, tempNode, oldKey); } } class LeafNode > extends Node { protected T[] values; protected LeafNode left; protected LeafNode right; public LeafNode() { this.values = (T[]) new Object[maxNumber]; } @Override T find(V key) { sum++; if (this.num == 0) { return null; } //二分查找 int left = 0; int right = this.num - 1; while (left <= right) { int mid = (left + right) / 2; int compare = key.compareTo((V) this.keys[mid]); if (compare == 0) { return values[mid]; } else if (compare > 0) { left = mid + 1; } else { right = mid - 1; } } return null; } @Override void updateRemove(BPlusTree bPlusTree) { //设计缺陷，这个其实是父类专属方法 } @Override T delete(V key, BPlusTree bPlusTree) { //二分查找 int left = 0; int right = this.num - 1; int value = -1; while (left <= right) { int mid = (left + right) / 2; int compare = key.compareTo((V) this.keys[mid]); if (compare == 0) { value = mid; break; } else if (compare > 0) { left = mid + 1; } else { right = mid - 1; } } if (value == -1) { return null; } T t = this.values[value]; //如果当前是根节点或者如果关键字大于m/2，则直接删除 if (this.parent == null || (this.num > bPlusTree.bTreeOrder / 2 && this.num > 2)) { for (int i = value; i < (this.num - 1); i++) { this.values[i] = this.values[i + 1]; } this.num--; return t; } //如果自身关键词小于等于m/2,并且前节点大于m/2,则从其处借补 if (this.left != null && this.left.parent == parent && this.left.num > bPlusTree.bTreeOrder / 2 && this.left.num > 2) { //借补最后一个值 T preLast = this.left.values[this.left.num - 1]; Object preLastKey = this.left.keys[this.left.num - 1]; //所有值往后移动一位，把第一位填充借补的值 for (int i = value; i > 0; i--) { this.values[i] = this.values[i - 1]; } this.values[0] = preLast; this.keys[0] = preLastKey; this.left.values[this.left.num - 1] = null; this.left.keys[this.left.num - 1] = null; this.left.num--; //父节点left节点的索引值做调整，为this.left.num-1的值 for (int i = 0; i <= this.parent.num; i++) { // 2 (0,1,2) // 7 (6,7) //删除6 //1 (0,1) //7 (2,6) if (this.parent.children[i] == this.left) { this.parent.keys[i] = this.left.keys[this.left.num - 1]; break; } } return t; } //如果自身关键词小于等于m/2，并且后节点大于m/2,则从其处借补 if (this.right != null && this.right.parent == parent && this.right.num > bPlusTree.bTreeOrder / 2 && this.right.num > 2) { //借补右边的第一个 T afterFirst = this.right.values[0]; Object afterFirstKey = this.right.keys[0]; for (int i = 0; i < (this.right.num - 1); i++) { this.right.values[i] = this.right.values[i + 1]; this.right.keys[i] = this.right.keys[i + 1]; } this.right.num--; this.num++; this.values[this.num - 1] = afterFirst; this.keys[this.num - 1] = afterFirstKey; //当前在父类中的索引值需要做调整，调整为最后一个值 for (int i = 0; i < this.parent.num; i++) { if (this.parent.children[i] == this) { this.parent.keys[i] = afterFirstKey; break; } } return t; } //同前面节点合并 if (this.left != null && this.left.parent == parent && (this.left.num <= bPlusTree.bTreeOrder / 2 || this.left.num <= 2)) { for (int i = 0; i < this.num; i++) { if (i != value) { this.left.num++; this.left.values[this.left.num - 1] = this.values[i]; this.left.keys[this.left.num - 1] = this.keys[i]; } } //删除prent里面的当前，并把当前的值赋给左节点 for (int i = 0; i <= this.parent.num; i++) { if (this.parent.children[i] == this) { //这里需要特别注意，left节点在父类中的索引值需要调整为最新的 this.parent.keys[i - 1] = this.parent.keys[i]; for (int j = i; j < (this.parent.num - 1); j++) { this.parent.children[j] = this.parent.children[j + 1]; this.parent.keys[j] = this.parent.keys[j + 1]; } this.parent.num--; } } //后继节点的关联关系重新绑定 this.left.right = this.right; if (this.right != null) { this.right.left = this.left; } //如果大于m/2个节点的话，不需要合并 if ((parent.parent != null && (parent.num >= bPlusTree.bTreeOrder / 2 && parent.num >= 2)) || (parent.parent == null && parent.num >= 2)) { return t; } //否则需要继续往上合并 parent.updateRemove(bPlusTree); return t; } //同后面节点合并 if (this.right != null && this.right.parent == this.parent && (this.right.num <= bPlusTree.bTreeOrder / 2 || this.right.num <= 2)) { //先把当前节点的值删除 for (int i = value; i < (this.num - 1); i++) { this.children[i] = this.children[i + 1]; this.keys[i] = this.keys[i + 1]; } this.num--; //然后把后面节点的值合并进来 for (int i = 0; i < this.right.num; i++) { this.num++; this.children[this.num - 1] = this.right.children[i]; this.keys[this.num - 1] = this.right.keys[i]; } //删除parent里面的right for (int i = 0; i <= this.parent.num; i++) { if (this.parent.children[i] == this.right) { this.parent.keys[i - 1] = this.parent.keys[i]; for (int j = i; j < (this.parent.num - 1); j++) { this.parent.children[j] = this.parent.children[j + 1]; this.parent.keys[j] = this.parent.keys[j + 1]; } this.parent.num--; } } LeafNode rightRight = this.right.right; this.right = null; if (rightRight != null) { this.right = rightRight; rightRight.left = this; } //如果大于m/2个节点的话，不需要合并 if ((parent.parent != null && (parent.num >= bPlusTree.bTreeOrder / 2 && parent.num >= 2)) || (parent.parent == null && parent.num >= 2)) { return t; } parent.updateRemove(bPlusTree); return t; } return null; } @Override List findByPre(String key) { if (this.num == 0) { return new LinkedList<>(); } //二分查找 int left = 0; int right = this.num - 1; while (left <= right) { int mid = (left + right) / 2; int compare = key.compareTo(this.keys[mid].toString()); if (compare == 0) { right = mid; break; } else if (compare > 0) { left = mid + 1; } else { right = mid - 1; } } List list = new LinkedList<>(); LeafNode leafNode = this; //这里需要特别注意，如果当前索引没有找到的情况下，结束的right节点可能是比key值小的，这种情况需要再判断一次 int start = key.compareTo(this.keys[right].toString()) > 0 ? (right + 1) : right; while (leafNode != null) { //循环每个节点内的值，如果节点值不存在了则继续，如果值存在但是不一样了，则结束 while (start < leafNode.num && leafNode.values[start] != null) { if (leafNode.keys[start].toString().startsWith(key)) { list.add((T) leafNode.values[start]); start++; continue; } return list; } start = 0; leafNode = leafNode.right; } return list; } @Override List findByRange(V startV, V endV) { //二分查找 int left = 0; int right = this.num - 1; //找到第一个大于等于start的值 while (left <= right) { int mid = (left + right) / 2; int compare = startV.compareTo((V) this.keys[mid]); if (compare == 0) { break; } else if (compare > 0) { left = mid + 1; } else { right = mid - 1; } } List list = new LinkedList<>(); LeafNode leafNode = this; //未查到特殊处理 int start = startV.compareTo((V) this.keys[left]) > 0 ? (left + 1) : left; while (leafNode != null) { //如果当前节点值不存在了，则继续下一个节点，如果比end值大了，则直接返回 while (start < leafNode.num && leafNode.values[start] != null) { if (((V) leafNode.keys[start]).compareTo(endV) < 0) { list.add((T) leafNode.values[start]); start++; continue; } return list; } start = 0; leafNode = leafNode.right; } return list; } @Override Node insert(V key, T value) { //这个是当前节点的最大值，也就是保存在父节点中的索引 V oldKey = this.num > 0 ? (V) this.keys[this.num - 1] : null; int i = 0; while (i < this.num) { if (key.compareTo((V) this.keys[i]) < 0) { break; } i++; } //生成新的数组，保存插入后的数组的值 Object[] tempKeys = new Object[maxNumber]; T[] tempValues = (T[]) new Object[maxNumber]; System.arraycopy(this.keys, 0, tempKeys, 0, i); System.arraycopy(this.values, 0, tempValues, 0, i); System.arraycopy(this.keys, i, tempKeys, i + 1, this.num - i); System.arraycopy(this.values, i, tempValues, i + 1, this.num - i); tempKeys[i] = key; tempValues[i] = value; this.num++; //如果当前节点没有达到结束，则无需分裂 Node node = this; if (this.num < bTreeOrder) { //把零时变量拷贝进去就可以了 System.arraycopy(tempKeys, 0, this.keys, 0, this.num); System.arraycopy(tempValues, 0, this.values, 0, this.num); V tempKey = (V) node.keys[node.num - 1]; while (node.parent != null) { //如果当前插入的变量值最大，会造成根据索引无法访问，需要更新索引为当前值 if (tempKey.compareTo((V) node.parent.keys[node.parent.num - 1]) > 0) { node.parent.keys[node.parent.num - 1] = tempKey; node = node.parent; } else { break; } } return null; } //下面的就是需要分裂的，从中间分裂成两个 int mid = this.num / 2; LeafNode tempNode = new LeafNode<>(); tempNode.num = this.num - mid; tempNode.parent = this.parent; //和右节点关联关系保存 if (this.right != null) { this.right.left = tempNode; } tempNode.right = this.right; //如果当前是根节点，需要造一个父节点 if (this.parent == null) { BPlusNode tempBPlusNode = new BPlusNode<>(); tempNode.parent = tempBPlusNode; this.parent = tempBPlusNode; oldKey = null; } System.arraycopy(tempKeys, mid, tempNode.keys, 0, tempNode.num); System.arraycopy(tempValues, mid, tempNode.values, 0, tempNode.num); //让原有叶子节点作为拆分的左半部分 this.num = mid; this.keys = new Object[maxNumber]; this.values = (T[]) new Object[maxNumber]; System.arraycopy(tempKeys, 0, this.keys, 0, mid); System.arraycopy(tempValues, 0, this.values, 0, mid); this.right = tempNode; tempNode.left = this; //叶子节点拆分成功后，需要把新的生成的节点插入父节点 BPlusNode parentNode = (BPlusNode ) this.parent; return parentNode.insertNode(this, tempNode, oldKey); } }}
例子
测试类
public class Person { private String name; private String desc; private int age; public Person(String name, String desc, Integer age) { this.name = name; this.desc = desc; if (age != null) { this.age = age; } } public String getName() { return name; } public void setName(String name) { this.name = name; } public String getDesc() { return desc; } public void setDesc(String desc) { this.desc = desc; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", desc='" + desc + '\'' + ", age=" + age + '}'; }} 测试组合索引类
public class CombinationIndexes implements Comparable { private Person person; public CombinationIndexes(Person person) { this.person = person; } public Person getPerson() { return person; } @Override public int compareTo(CombinationIndexes o) { int value = person.getName().compareTo(o.getPerson().getName()); if (value != 0) { return value; } return person.getDesc().compareTo(o.getPerson().getDesc()); }}
测试代码
public class Main { public static BPlusTree initTree() { BPlusTree bPlusTree = new BPlusTree<>(); bPlusTree.insert("占旭鹏", new Person("占旭鹏", "占旭鹏测试", 12)); bPlusTree.insert("占", new Person("占", "占旭鹏测试", 12)); bPlusTree.insert("占11", new Person("占11", "占旭鹏测试", 12)); bPlusTree.insert("占旭鹏测试", new Person("占旭鹏测试", "占旭鹏测试", 12)); bPlusTree.insert("占其他测试", new Person("占其他测试", "占旭鹏测试", 12)); bPlusTree.insert("占其他", new Person("占其他", "占旭鹏测试", 12)); bPlusTree.insert("占吃", new Person("占吃", "占旭鹏测试", 12)); bPlusTree.insert("占23213", new Person("占23213", "占旭鹏测试", 12)); bPlusTree.insert("占发顺丰的", new Person("占发顺丰的", "占旭鹏测试", 12)); bPlusTree.insert("占方式", new Person("占方式", "占旭鹏测试", 12)); bPlusTree.insert("其他", new Person("其他", "测试", 12)); return bPlusTree; } /** * 模拟删除 */ public static void printDelete(BPlusTree tree, String key) { Person person = tree.delete(key); System.out.println("-------------delete-------------------"); System.out.println(person); System.out.println("-------------delete-------------------"); System.out.println(); } /** * 模拟索引查询 */ public static void printFind(BPlusTree tree, String key) { Person person = tree.find(key); System.out.println("-------------printFind-------------------"); System.out.println(person); System.out.println("-------------printFind-------------------"); System.out.println(); } /** * 模拟like */ public static void printFindByPre(BPlusTree tree, String pre) { List list = tree.findByPre(pre); System.out.println("-------------findByPre-------------------"); System.out.println(list); System.out.println("-------------findByPre-------------------"); System.out.println(); } /** * 模拟范围查询 */ public static void printFindByRange(BPlusTree tree, String start, String end) { List list = tree.findByRange(start, end); System.out.println("-------------findByRange-----------------"); System.out.println(list); System.out.println("-------------findByRange-----------------"); } /** * 组合索引查询 */ public static void printCombinationIndexes() { BPlusTree bPlusTree = new BPlusTree<>(); Person person = new Person("占旭鹏", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占11", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占旭鹏测试", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占其他测试", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占其他", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占吃", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占23213", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占发顺丰的", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占方式", "占旭鹏测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("其他", "测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); person = new Person("占其他他", "测试", 12); bPlusTree.insert(new CombinationIndexes(person), person); Person personStart = new Person("占其", null, null); Person personEnd = new Person("占其他她1", null, null); System.out.println(); System.out.println("-------------printCombinationIndexes-----------------"); List list = bPlusTree.findByRange(new CombinationIndexes(personStart), new CombinationIndexes(personEnd)); System.out.println(list); System.out.println(); personStart = new Person("占其他", "占旭鹏", null); personEnd = new Person("占其他", "占旭鹏测试11", null); list = bPlusTree.findByRange(new CombinationIndexes(personStart), new CombinationIndexes(personEnd)); System.out.println(list); System.out.println(); personStart = new Person("占其他", "占旭鹏", null); personEnd = new Person("占其他", "占旭鹏测", null); list = bPlusTree.findByRange(new CombinationIndexes(personStart), new CombinationIndexes(personEnd)); System.out.println(list); System.out.println(); System.out.println("-------------printCombinationIndexes-----------------"); } public static void main(String[] args) { BPlusTree bPlusTree = initTree(); printDelete(bPlusTree, "占旭鹏"); printFind(bPlusTree, "占旭鹏"); printFind(bPlusTree, "占"); printFindByPre(bPlusTree, "占"); printFindByPre(bPlusTree, "占旭鹏"); printFindByRange(bPlusTree, "占旭鹏", "占旭鹏测试11"); printCombinationIndexes(); }} 性能测试代码
public class BPlusTreeTest { /** * 性能测试 */ public static void testNum(int allNum) { //生成随机数 List testNum = new LinkedList<>(); for (int i = 0; i < 100; i++) { testNum.add(new Random().nextInt(allNum)); testNum.add(new Random().nextInt(allNum * 10)); } long time = System.currentTimeMillis(); BPlusTree bPlusTree = new BPlusTree<>(10); for (int i = 0; i < allNum; i++) { bPlusTree.insert(i, i + "测试"); } testNum.forEach(bPlusTree::find); System.out.println("b+树总共查询的次数" + bPlusTree.sum); System.out.println("b+树消耗的时间：" + (System.currentTimeMillis() - time)); time = System.currentTimeMillis(); List > list = new LinkedList<>(); for (int i = 0; i < allNum; i++) { list.add(new Pair<>(i, i + "测试")); } testNum.forEach(x -> list.stream().filter(y -> y.getKey().equals(x)).findAny()); System.out.println("列表中共消耗的时间：" + (System.currentTimeMillis() - time)); time = System.currentTimeMillis(); testNum.forEach(bPlusTree::find); System.out.println("b+树查询消耗的时间：" + (System.currentTimeMillis() - time)); time = System.currentTimeMillis(); testNum.forEach(x -> list.stream().filter(y -> y.getKey().equals(x)).findAny()); System.out.println("列表查询消耗的时间：" + (System.currentTimeMillis() - time)); } public static void main(String[] args) { testNum(10000000); }} 转载地址：http://qsjqi.baihongyu.com/