devbox
Li_阴宅
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

B+树的Java实现_b+树java实现

作者：Li_阴宅 | 2024-08-20 11:52:31

赞

踩

b+树java实现

下面的B+树算法是在我学习了别人的代码之后经过修改完成的，主要在叶子节点上使用了二分查找，另外在更新节点上也减少了部分的递归操作，还对节点的结构做了细微的修改（每个节点得孩子指针比关键码多1，原来是孩子指针和关键码一样多，这也与B+树的原本定义一致），应该说整个程序的逻辑比原来清晰了一些。在此特别感谢wguoyong作者！大家可以参考原博主的代码点击打开链接

在写B+树的过程中，其实查询和插入操作都不算很难，最难的是删除操作，在做中间节点合并的时候需要特别注意关键字和孩子指针的更新，具体见代码。

    我对改进后的算法与之前的做了比较，下面的测试我在Macbook air  OS X 10.9.2上做的测试：

 

阶数10阶

修改前

修改后

随机插入100万条数据

4100ms

2200ms

顺序插入100万条数据

1800ms

940ms

随机查询100万次数据

2800ms

1350ms

顺序查询100万次数据

730ms

250ms

随机删除100万次数据

4600ms

1400ms

顺序删除100万次数据

20­­00ms

450ms

 

 

 

 阶数100阶

修改前

修改后

随机插入100万条数据

8100ms

2100ms

顺序插入100万条数据

4300ms

700ms

随机查询100万次数据

2000ms

1200ms

顺序查询100万次数据

850ms

250ms

随机删除100万次数据

8000ms

1500ms

顺序删除100万次数据

4500ms

300ms

 

源代码：

BplusTree.java


  1. /**
  2.  * B+树的定义：
  3.  * 
  4.  * 1.任意非叶子结点最多有M个子节点；且M>2；M为B+树的阶数
  5.  * 2.除根结点以外的非叶子结点至少有 (M+1)/2个子节点；
  6.  * 3.根结点至少有2个子节点；
  7.  * 4.除根节点外每个结点存放至少（M-1）/2和至多M-1个关键字；（至少1个关键字）
  8.  * 5.非叶子结点的子树指针比关键字多1个；
  9.  * 6.非叶子节点的所有key按升序存放，假设节点的关键字分别为K[0], K[1] … K[M-2], 
  10.  *  指向子女的指针分别为P[0], P[1]…P[M-1]。则有：
  11.  *  P[0] < K[0] <= P[1] < K[1] …..< K[M-2] <= P[M-1]
  12.  * 7.所有叶子结点位于同一层；
  13.  * 8.为所有叶子结点增加一个链指针；
  14.  * 9.所有关键字都在叶子结点出现
  15.  */
  16. /**
  17.  * @author LeeJay 2014-04-03
  18.  *
  19.  */
  20.  
  21. import java.util.ArrayList;
  22. import java.util.List;
  23. import java.util.Random;
  24.  
  25. public class BplusTree <K extends Comparable<K>, V>{
  26.  
  27. 	/** 根节点 */
  28. 	protected BplusNode<K, V> root;
  29.  
  30. 	/** 阶数，M值 */
  31. 	protected int order;
  32.  
  33. 	/** 叶子节点的链表头 */
  34. 	protected BplusNode<K, V> head;
  35.  
  36. 	/** 树高*/
  37. 	protected int height = 0;
  38. 	
  39. 	public BplusNode<K, V> getHead() {
  40. 		return head;
  41. 	}
  42.  
  43. 	public void setHead(BplusNode<K, V> head) {
  44. 		this.head = head;
  45. 	}
  46.  
  47. 	public BplusNode<K, V> getRoot() {
  48. 		return root;
  49. 	}
  50.  
  51. 	public void setRoot(BplusNode<K, V> root) {
  52. 		this.root = root;
  53. 	}
  54.  
  55. 	public int getOrder() {
  56. 		return order;
  57. 	}
  58.  
  59. 	public void setOrder(int order) {
  60. 		this.order = order;
  61. 	}
  62. 	
  63. 	public void setHeight(int height) {
  64. 		this.height = height;
  65. 	}
  66. 	
  67. 	public int getHeight() {
  68. 		return height;
  69. 	}
  70. 	
  71. 	public V get(K key) {
  72. 		return root.get(key);
  73. 	}
  74.  
  75. 	public V remove(K key) {
  76. 		return root.remove(key, this);
  77. 	}
  78.  
  79. 	public void insertOrUpdate(K key, V value) {
  80. 		root.insertOrUpdate(key, value, this);
  81.  
  82. 	}
  83.  
  84. 	public BplusTree(int order) {
  85. 		if (order < 3) {
  86. 			System.out.print("order must be greater than 2");
  87. 			System.exit(0);
  88. 		}
  89. 		this.order = order;
  90. 		root = new BplusNode<K, V>(true, true);
  91. 		head = root;
  92. 	}
  93.  
  94. 	// 测试
  95. 	public static void main(String[] args) {
  96.  
  97. 		int size = 1000000;
  98. 		int order = 100;
  99. //		 testRandomInsert(size, order);
  100. //
  101. //		 testOrderInsert(size, order);
  102. //
  103. //		 testRandomSearch(size, order);
  104. //
  105. //		 testOrderSearch(size, order);
  106. //
  107. //		 testRandomRemove(size, order);
  108. //
  109. //		 testOrderRemove(size, order);
  110. 	}
  111.  
  112. 	private static void testOrderRemove(int size, int order) {
  113. 		BplusTree<Integer, Integer> tree = new BplusTree<Integer, Integer>(order);
  114. 		System.out.println("\nTest order remove " + size + " datas, of order:"
  115. 				+ order);
  116. 		System.out.println("Begin order insert...");
  117. 		for (int i = 0; i < size; i++) {
  118. 			tree.insertOrUpdate(i, i);
  119. 		}
  120. 		System.out.println("Begin order remove...");
  121. 		long current = System.currentTimeMillis();
  122. 		for (int j = 0; j < size; j++) {
  123. 			if (tree.remove(j) == null) {
  124. 				System.err.println("得不到数据:" + j);
  125. 				break;
  126. 			}
  127. 		}
  128. 		long duration = System.currentTimeMillis() - current;
  129. 		System.out.println("time elpsed for duration: " + duration);
  130. 		System.out.println(tree.getHeight());
  131. 	}
  132.  
  133. 	private static void testRandomRemove(int size, int order) {
  134. 		BplusTree<Integer, Integer> tree = new BplusTree<Integer, Integer>(order);
  135. 		System.out.println("\nTest random remove " + size + " datas, of order:"
  136. 				+ order);
  137. 		Random random = new Random();
  138. 		boolean[] a = new boolean[size + 10];
  139. 		List<Integer> list = new ArrayList<Integer>();
  140. 		int randomNumber = 0;
  141. 		System.out.println("Begin random insert...");
  142. 		for (int i = 0; i < size; i++) {
  143. 			randomNumber = random.nextInt(size);
  144. 			a[randomNumber] = true;
  145. 			list.add(randomNumber);
  146. 			tree.insertOrUpdate(randomNumber, randomNumber);
  147. 		}
  148. 		System.out.println("Begin random remove...");
  149. 		long current = System.currentTimeMillis();
  150. 		for (int j = 0; j < size; j++) {
  151. 			randomNumber = list.get(j);
  152. 			if (a[randomNumber]) {
  153. 				if (tree.remove(randomNumber) == null) {
  154. 					System.err.println("得不到数据:" + randomNumber);
  155. 					break;
  156. 				} else {
  157. 					a[randomNumber] = false;
  158. 				}
  159. 			}
  160. 		}
  161. 		long duration = System.currentTimeMillis() - current;
  162. 		System.out.println("time elpsed for duration: " + duration);
  163. 		System.out.println(tree.getHeight());
  164. 	}
  165.  
  166. 	private static void testOrderSearch(int size, int order) {
  167. 		BplusTree<Integer, Integer> tree = new BplusTree<Integer, Integer>(order);
  168. 		System.out.println("\nTest order search " + size + " datas, of order:"
  169. 				+ order);
  170. 		System.out.println("Begin order insert...");
  171. 		for (int i = 0; i < size; i++) {
  172. 			tree.insertOrUpdate(i, i);
  173. 		}
  174. 		System.out.println("Begin order search...");
  175. 		long current = System.currentTimeMillis();
  176. 		for (int j = 0; j < size; j++) {
  177. 			if (tree.get(j) == null) {
  178. 				System.err.println("得不到数据:" + j);
  179. 				break;
  180. 			}
  181. 		}
  182. 		long duration = System.currentTimeMillis() - current;
  183. 		System.out.println("time elpsed for duration: " + duration);
  184. 	}
  185.  
  186. 	private static void testRandomSearch(int size, int order) {
  187. 		BplusTree<Integer, Integer> tree = new BplusTree<Integer, Integer>(order);
  188. 		System.out.println("\nTest random search " + size + " datas, of order:"
  189. 				+ order);
  190. 		Random random = new Random();
  191. 		boolean[] a = new boolean[size + 10];
  192. 		int randomNumber = 0;
  193. 		System.out.println("Begin random insert...");
  194. 		for (int i = 0; i < size; i++) {
  195. 			randomNumber = random.nextInt(size);
  196. 			a[randomNumber] = true;
  197. 			tree.insertOrUpdate(randomNumber, randomNumber);
  198. 		}
  199. 		System.out.println("Begin random search...");
  200. 		long current = System.currentTimeMillis();
  201. 		for (int j = 0; j < size; j++) {
  202. 			randomNumber = random.nextInt(size);
  203. 			if (a[randomNumber]) {
  204. 				if (tree.get(randomNumber) == null) {
  205. 					System.err.println("得不到数据:" + randomNumber);
  206. 					break;
  207. 				}
  208. 			}
  209. 		}
  210. 		long duration = System.currentTimeMillis() - current;
  211. 		System.out.println("time elpsed for duration: " + duration);
  212. 	}
  213.  
  214. 	private static void testRandomInsert(int size, int order) {
  215. 		BplusTree<Integer, Integer> tree = new BplusTree<Integer, Integer>(order);
  216. 		System.out.println("\nTest random insert " + size + " datas, of order:"
  217. 				+ order);
  218. 		Random random = new Random();
  219. 		int randomNumber = 0;
  220. 		long current = System.currentTimeMillis();
  221. 		for (int i = 0; i < size; i++) {
  222. 			randomNumber = random.nextInt(size);
  223. 			tree.insertOrUpdate(randomNumber, randomNumber);
  224. 		}
  225. 		long duration = System.currentTimeMillis() - current;
  226. 		System.out.println("time elpsed for duration: " + duration);
  227. 		
  228. 		System.out.println(tree.getHeight());
  229. 	}
  230.  
  231. 	private static void testOrderInsert(int size, int order) {
  232. 		BplusTree<Integer, Integer> tree = new BplusTree<Integer, Integer>(order);
  233. 		System.out.println("\nTest order insert " + size + " datas, of order:"
  234. 				+ order);
  235. 		long current = System.currentTimeMillis();
  236. 		for (int i = 0; i < size; i++) {
  237. 			tree.insertOrUpdate(i, i);
  238. 		}
  239. 		long duration = System.currentTimeMillis() - current;
  240. 		System.out.println("time elpsed for duration: " + duration);
  241. 	}
  242. }


BplusNode.java 

  1. import java.util.AbstractMap.SimpleEntry; 
  2. import java.util.ArrayList; 
  3. import java.util.List; 
  4. import java.util.Map.Entry; 
  5.  
  6. public class BplusNode <K extends Comparable<K>, V> { 
  7.      
  8.     /** 是否为叶子节点 */ 
  9.     protected boolean isLeaf; 
  10.      
  11.     /** 是否为根节点*/ 
  12.     protected boolean isRoot; 
  13.  
  14.     /** 父节点 */ 
  15.     protected BplusNode<K, V> parent; 
  16.      
  17.     /** 叶节点的前节点*/ 
  18.     protected BplusNode<K, V> previous; 
  19.      
  20.     /** 叶节点的后节点*/ 
  21.     protected BplusNode<K, V> next;     
  22.      
  23.     /** 节点的关键字 */ 
  24.     protected List<Entry<K, V>> entries; 
  25.      
  26.     /** 子节点 */ 
  27.     protected List<BplusNode<K, V>> children; 
  28.      
  29.     public BplusNode(boolean isLeaf) { 
  30.         this.isLeaf = isLeaf; 
  31.         entries = new ArrayList<Entry<K, V>>(); 
  32.          
  33.         if (!isLeaf) { 
  34.             children = new ArrayList<BplusNode<K, V>>(); 
  35.         } 
  36.     } 
  37.  
  38.     public BplusNode(boolean isLeaf, boolean isRoot) { 
  39.         this(isLeaf); 
  40.         this.isRoot = isRoot; 
  41.     } 
  42.      
  43.     public V get(K key) { 
  44.          
  45.         //如果是叶子节点 
  46.         if (isLeaf) { 
  47. 	        	int low = 0, high = entries.size() - 1, mid;
  48. 	            int comp ;
  49. 	    		while (low <= high) {
  50. 	    			mid = (low + high) / 2;
  51. 	    			comp = entries.get(mid).getKey().compareTo(key);
  52. 	    			if (comp == 0) {
  53. 	    				return entries.get(mid).getValue();
  54. 	    			} else if (comp < 0) {
  55. 	    				low = mid + 1;
  56. 	    			} else {
  57. 	    				high = mid - 1;
  58. 	    			}
  59. 	    		}
  60.             //未找到所要查询的对象 
  61.             return null; 
  62.         }
  63.         //如果不是叶子节点 
  64.         //如果key小于节点最左边的key，沿第一个子节点继续搜索 
  65.         if (key.compareTo(entries.get(0).getKey()) < 0) { 
  66.             return children.get(0).get(key); 
  67.         //如果key大于等于节点最右边的key，沿最后一个子节点继续搜索 
  68.         }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { 
  69.             return children.get(children.size()-1).get(key); 
  70.         //否则沿比key大的前一个子节点继续搜索 
  71.         }else { 
  72.             int low = 0, high = entries.size() - 1, mid= 0;
  73.             int comp ;
  74.         		while (low <= high) {
  75.         			mid = (low + high) / 2;
  76.         			comp = entries.get(mid).getKey().compareTo(key);
  77.         			if (comp == 0) {
  78.         				return children.get(mid+1).get(key); 
  79.         			} else if (comp < 0) {
  80.         				low = mid + 1;
  81.         			} else {
  82.         				high = mid - 1;
  83.         			}
  84.         		}
  85.         		return children.get(low).get(key);
  86.         } 
  87.     } 
  88.      
  89.     public void insertOrUpdate(K key, V value, BplusTree<K,V> tree){ 
  90.         //如果是叶子节点 
  91.         if (isLeaf){ 
  92.             //不需要分裂，直接插入或更新 
  93.             if (contains(key) != -1 || entries.size() < tree.getOrder()){ 
  94.                 insertOrUpdate(key, value); 
  95.                 if(tree.getHeight() == 0){
  96.                 		tree.setHeight(1);
  97.                 }
  98.                 return ;
  99.             }
  100.             	//需要分裂 
  101.             //分裂成左右两个节点 
  102.             BplusNode<K,V> left = new BplusNode<K,V>(true); 
  103.             BplusNode<K,V> right = new BplusNode<K,V>(true); 
  104.             //设置链接 
  105.             if (previous != null){ 
  106.                 previous.next = left; 
  107.                 left.previous = previous ; 
  108.             } 
  109.             if (next != null) { 
  110.                 next.previous = right; 
  111.                 right.next = next; 
  112.             } 
  113.             if (previous == null){ 
  114.                 tree.setHead(left); 
  115.             } 
  116.  
  117.             left.next = right; 
  118.             right.previous = left; 
  119.             previous = null; 
  120.             next = null; 
  121.              
  122.             //复制原节点关键字到分裂出来的新节点 
  123.             copy2Nodes(key, value, left, right, tree);
  124.             
  125.             //如果不是根节点 
  126.             if (parent != null) { 
  127.                 //调整父子节点关系 
  128.                 int index = parent.children.indexOf(this); 
  129.                 parent.children.remove(this); 
  130.                 left.parent = parent; 
  131.                 right.parent = parent; 
  132.                 parent.children.add(index,left); 
  133.                 parent.children.add(index + 1, right); 
  134.                 parent.entries.add(index,right.entries.get(0));
  135.                 entries = null; //删除当前节点的关键字信息
  136.                 children = null; //删除当前节点的孩子节点引用
  137.                  
  138.                 //父节点插入或更新关键字 
  139.                 parent.updateInsert(tree); 
  140.                 parent = null; //删除当前节点的父节点引用
  141.             //如果是根节点     
  142.             }else { 
  143.                 isRoot = false; 
  144.                 BplusNode<K,V> parent = new BplusNode<K,V> (false, true); 
  145.                 tree.setRoot(parent); 
  146.                 left.parent = parent; 
  147.                 right.parent = parent; 
  148.                 parent.children.add(left); 
  149.                 parent.children.add(right);
  150.                 parent.entries.add(right.entries.get(0));
  151.                 entries = null; 
  152.                 children = null; 
  153.             } 
  154.             return ;
  155.          
  156.         }
  157.         //如果不是叶子节点
  158.         //如果key小于等于节点最左边的key，沿第一个子节点继续搜索 
  159.         if (key.compareTo(entries.get(0).getKey()) < 0) { 
  160.             children.get(0).insertOrUpdate(key, value, tree); 
  161.         //如果key大于节点最右边的key，沿最后一个子节点继续搜索 
  162.         }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { 
  163.             children.get(children.size()-1).insertOrUpdate(key, value, tree); 
  164.         //否则沿比key大的前一个子节点继续搜索 
  165.         }else { 
  166.             int low = 0, high = entries.size() - 1, mid= 0;
  167.             int comp ;
  168.         		while (low <= high) {
  169.         			mid = (low + high) / 2;
  170.         			comp = entries.get(mid).getKey().compareTo(key);
  171.         			if (comp == 0) {
  172.         				children.get(mid+1).insertOrUpdate(key, value, tree);
  173.         				break;
  174.         			} else if (comp < 0) {
  175.         				low = mid + 1;
  176.         			} else {
  177.         				high = mid - 1;
  178.         			}
  179.         		}
  180.         		if(low>high){
  181.         			children.get(low).insertOrUpdate(key, value, tree);
  182.         		}
  183.         } 
  184.     }
  185.  
  186. 	private void copy2Nodes(K key, V value, BplusNode<K,V> left,
  187. 			BplusNode<K,V> right,BplusTree<K,V> tree) {
  188. 		//左右两个节点关键字长度 
  189.         int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2; 
  190. 		boolean b = false;//用于记录新元素是否已经被插入
  191. 		for (int i = 0; i < entries.size(); i++) {
  192. 			if(leftSize !=0){
  193. 				leftSize --;
  194. 				if(!b&&entries.get(i).getKey().compareTo(key) > 0){
  195. 					left.entries.add(new SimpleEntry<K, V>(key, value));
  196. 					b = true;
  197. 					i--;
  198. 				}else {
  199. 					left.entries.add(entries.get(i));
  200. 				}
  201. 			}else {
  202. 				if(!b&&entries.get(i).getKey().compareTo(key) > 0){
  203. 					right.entries.add(new SimpleEntry<K, V>(key, value));
  204. 					b = true;
  205. 					i--;
  206. 				}else {
  207. 					right.entries.add(entries.get(i));
  208. 				}
  209. 			}
  210. 		}
  211. 		if(!b){
  212. 			right.entries.add(new SimpleEntry<K, V>(key, value));
  213. 		}
  214. 	} 
  215.      
  216.     /** 插入节点后中间节点的更新 */ 
  217.     protected void updateInsert(BplusTree<K,V> tree){ 
  218.          
  219.         //如果子节点数超出阶数，则需要分裂该节点    
  220.         if (children.size() > tree.getOrder()) { 
  221.             //分裂成左右两个节点 
  222.             BplusNode<K, V> left = new BplusNode<K, V>(false); 
  223.             BplusNode<K, V> right = new BplusNode<K, V>(false); 
  224.             //左右两个节点子节点的长度 
  225.             int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2; 
  226.             int rightSize = (tree.getOrder() + 1) / 2; 
  227.             //复制子节点到分裂出来的新节点，并更新关键字 
  228.             for (int i = 0; i < leftSize; i++){ 
  229.                 left.children.add(children.get(i)); 
  230.                 children.get(i).parent = left; 
  231.             } 
  232.             for (int i = 0; i < rightSize; i++){ 
  233.                 right.children.add(children.get(leftSize + i)); 
  234.                 children.get(leftSize + i).parent = right; 
  235.             } 
  236.             for (int i = 0; i < leftSize - 1; i++) {
  237.             		left.entries.add(entries.get(i)); 
  238. 			}
  239.             for (int i = 0; i < rightSize - 1; i++) {
  240.             		right.entries.add(entries.get(leftSize + i)); 
  241. 			}
  242.             
  243.             //如果不是根节点 
  244.             if (parent != null) { 
  245.                 //调整父子节点关系 
  246.                 int index = parent.children.indexOf(this); 
  247.                 parent.children.remove(this); 
  248.                 left.parent = parent; 
  249.                 right.parent = parent; 
  250.                 parent.children.add(index,left); 
  251.                 parent.children.add(index + 1, right); 
  252.                 parent.entries.add(index,entries.get(leftSize - 1));
  253.                 entries = null; 
  254.                 children = null; 
  255.                  
  256.                 //父节点更新关键字 
  257.                 parent.updateInsert(tree); 
  258.                 parent = null; 
  259.             //如果是根节点     
  260.             }else { 
  261.                 isRoot = false; 
  262.                 BplusNode<K, V> parent = new BplusNode<K, V>(false, true); 
  263.                 tree.setRoot(parent);
  264.                 tree.setHeight(tree.getHeight() + 1);
  265.                 left.parent = parent; 
  266.                 right.parent = parent; 
  267.                 parent.children.add(left); 
  268.                 parent.children.add(right); 
  269.                 parent.entries.add(entries.get(leftSize - 1));
  270.                 entries = null; 
  271.                 children = null; 
  272.             } 
  273.         }
  274.     } 
  275.      
  276.     /** 删除节点后中间节点的更新*/ 
  277.     protected void updateRemove(BplusTree<K,V> tree) { 
  278.  
  279.         // 如果子节点数小于M / 2或者小于2，则需要合并节点 
  280.         if (children.size() < tree.getOrder() / 2 || children.size() < 2) { 
  281.             if (isRoot) { 
  282.                 // 如果是根节点并且子节点数大于等于2，OK 
  283.                 if (children.size() >= 2) return; 
  284.                 // 否则与子节点合并 
  285.                 BplusNode<K, V> root = children.get(0); 
  286.                 tree.setRoot(root); 
  287.                 tree.setHeight(tree.getHeight() - 1);
  288.                 root.parent = null; 
  289.                 root.isRoot = true; 
  290.                 entries = null; 
  291.                 children = null; 
  292.                 return ;
  293.             } 
  294.             //计算前后节点  
  295.             int currIdx = parent.children.indexOf(this); 
  296.             int prevIdx = currIdx - 1; 
  297.             int nextIdx = currIdx + 1; 
  298.             BplusNode<K, V> previous = null, next = null; 
  299.             if (prevIdx >= 0) { 
  300.                 previous = parent.children.get(prevIdx); 
  301.             } 
  302.             if (nextIdx < parent.children.size()) { 
  303.                 next = parent.children.get(nextIdx); 
  304.             } 
  305.              
  306.             // 如果前节点子节点数大于M / 2并且大于2，则从其处借补 
  307.             if (previous != null  
  308.                     && previous.children.size() > tree.getOrder() / 2 
  309.                     && previous.children.size() > 2) { 
  310.                 //前叶子节点末尾节点添加到首位 
  311.                 int idx = previous.children.size() - 1; 
  312.                 BplusNode<K, V> borrow = previous.children.get(idx); 
  313.                 previous.children.remove(idx); 
  314.                 borrow.parent = this; 
  315.                 children.add(0, borrow);
  316.                 int preIndex = parent.children.indexOf(previous);
  317.                 
  318.                 entries.add(0,parent.entries.get(preIndex));
  319.                 parent.entries.set(preIndex, previous.entries.remove(idx - 1));
  320.                 return ;
  321.             }
  322.             
  323.             // 如果后节点子节点数大于M / 2并且大于2，则从其处借补
  324.             if (next != null  
  325.                     && next.children.size() > tree.getOrder() / 2 
  326.                     && next.children.size() > 2) { 
  327.                 //后叶子节点首位添加到末尾 
  328.                 BplusNode<K, V> borrow = next.children.get(0); 
  329.                 next.children.remove(0); 
  330.                 borrow.parent = this; 
  331.                 children.add(borrow); 
  332.                 int preIndex = parent.children.indexOf(this);
  333.                 entries.add(parent.entries.get(preIndex));
  334.                 parent.entries.set(preIndex, next.entries.remove(0));
  335.                 return ;
  336.             }
  337.             
  338.             // 同前面节点合并 
  339.             if (previous != null  
  340.                     && (previous.children.size() <= tree.getOrder() / 2 
  341.                     || previous.children.size() <= 2)) { 
  342.                 for (int i = 0; i < children.size(); i++) {
  343.                     previous.children.add(children.get(i)); 
  344. 				}
  345.                 for(int i = 0; i < previous.children.size();i++){
  346.                 		previous.children.get(i).parent = this;
  347.                 }
  348.                 int indexPre = parent.children.indexOf(previous);
  349.                 previous.entries.add(parent.entries.get(indexPre));
  350.                 for (int i = 0; i < entries.size(); i++) {
  351. 					previous.entries.add(entries.get(i));
  352. 				}
  353.                 children = previous.children;
  354.                 entries = previous.entries;
  355.                 
  356.                 //更新父节点的关键字列表
  357.                 parent.children.remove(previous);
  358.                 previous.parent = null;
  359.                 previous.children = null;
  360.                 previous.entries = null;
  361.                 parent.entries.remove(parent.children.indexOf(this));
  362.                 if((!parent.isRoot 
  363.                 			&& (parent.children.size() >= tree.getOrder() / 2
  364.                 			&& parent.children.size() >= 2))
  365.                 			||parent.isRoot && parent.children.size() >= 2){
  366. 	                 return ;
  367. 				}
  368.                 parent.updateRemove(tree); 
  369.                 return ;
  370.             }   
  371.             
  372. 	        // 同后面节点合并 
  373.             if (next != null  
  374.                     && (next.children.size() <= tree.getOrder() / 2 
  375.                     || next.children.size() <= 2)) { 
  376.                 for (int i = 0; i < next.children.size(); i++) { 
  377.                     BplusNode<K, V> child = next.children.get(i); 
  378.                     children.add(child); 
  379.                     child.parent = this; 
  380.                 } 
  381.                 int index = parent.children.indexOf(this);
  382.                 entries.add(parent.entries.get(index));
  383.                 for (int i = 0; i < next.entries.size(); i++) {
  384. 					entries.add(next.entries.get(i));
  385. 				}
  386.                 parent.children.remove(next);
  387.                 next.parent = null;
  388.                 next.children = null;
  389.                 next.entries = null;
  390.                 parent.entries.remove(parent.children.indexOf(this));
  391.                 if((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
  392.                 			&& parent.children.size() >= 2))
  393.                 			||parent.isRoot && parent.children.size() >= 2){
  394. 	                 return ;
  395. 				}
  396.                 parent.updateRemove(tree); 
  397.                 return ;
  398.             } 
  399.         } 
  400.     } 
  401.      
  402.     public V remove(K key, BplusTree<K,V> tree){ 
  403.         //如果是叶子节点 
  404.         if (isLeaf){ 
  405.             //如果不包含该关键字，则直接返回 
  406.             if (contains(key) == -1){ 
  407.                 return null; 
  408.             } 
  409.             //如果既是叶子节点又是根节点，直接删除 
  410.             if (isRoot) { 
  411.             		if(entries.size() == 1){
  412.             			tree.setHeight(0);
  413.             		}
  414.                 return remove(key); 
  415.             }
  416.             //如果关键字数大于M / 2，直接删除 
  417.             if (entries.size() > tree.getOrder() / 2 && entries.size() > 2) { 
  418.                return remove(key); 
  419.             }
  420.             //如果自身关键字数小于M / 2，并且前节点关键字数大于M / 2，则从其处借补 
  421.             if (previous != null &&  
  422.             		    previous.parent == parent
  423.                     && previous.entries.size() > tree.getOrder() / 2 
  424.                     && previous.entries.size() > 2 ) { 
  425.                 //添加到首位 
  426.             		int size = previous.entries.size(); 
  427.                 entries.add(0, previous.entries.remove(size - 1)); 
  428.                 int index = parent.children.indexOf(previous);
  429.                 parent.entries.set(index, entries.get(0));
  430.                 return remove(key);
  431.             }
  432.             //如果自身关键字数小于M / 2，并且后节点关键字数大于M / 2，则从其处借补 
  433.             if (next != null 
  434.             				&& next.parent == parent 
  435.                         && next.entries.size() > tree.getOrder() / 2 
  436.                         && next.entries.size() > 2) { 
  437.                 entries.add(next.entries.remove(0)); 
  438.                 int index = parent.children.indexOf(this);
  439.                 parent.entries.set(index, next.entries.get(0));
  440.                 return remove(key);
  441.             }
  442.             	
  443.             //同前面节点合并 
  444.             if (previous != null	 
  445.             			&& previous.parent == parent 
  446.                     && (previous.entries.size() <= tree.getOrder() / 2 
  447.                     || previous.entries.size() <= 2)) { 
  448.             		V returnValue =  remove(key);
  449.                 for (int i = 0; i < entries.size(); i++) { 
  450.                     //将当前节点的关键字添加到前节点的末尾
  451.                 		previous.entries.add(entries.get(i));
  452.                 } 
  453.                 entries = previous.entries;
  454.                 parent.children.remove(previous);
  455.                 previous.parent = null; 
  456.                 previous.entries = null;
  457.                 //更新链表 
  458.                 if (previous.previous != null) { 
  459.                     BplusNode<K, V> temp = previous; 
  460.                     temp.previous.next = this; 
  461.                     previous = temp.previous; 
  462.                     temp.previous = null; 
  463.                     temp.next = null;                          
  464.                 }else { 
  465.                     tree.setHead(this); 
  466.                     previous.next = null; 
  467.                     previous = null; 
  468.                 }
  469.                 parent.entries.remove(parent.children.indexOf(this));
  470.                 if((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
  471.                 			&& parent.children.size() >= 2))
  472.                 			||parent.isRoot && parent.children.size() >= 2){
  473.                 	 	return returnValue;
  474.                 }
  475.                 parent.updateRemove(tree);
  476.                 return returnValue;
  477.             }
  478.             //同后面节点合并
  479.             if(next != null  
  480.             			&& next.parent == parent
  481. 	                && (next.entries.size() <= tree.getOrder() / 2 
  482. 	                || next.entries.size() <= 2)) { 
  483.             		V returnValue = remove(key); 
  484. 	            for (int i = 0; i < next.entries.size(); i++) { 
  485. 	                //从首位开始添加到末尾 
  486. 	                entries.add(next.entries.get(i)); 
  487. 	            } 
  488. 	            next.parent = null; 
  489. 	            next.entries = null;
  490. 	            parent.children.remove(next); 
  491. 	            //更新链表 
  492. 	            if (next.next != null) { 
  493. 	                BplusNode<K, V> temp = next; 
  494. 	                temp.next.previous = this; 
  495. 	                next = temp.next; 
  496. 	                temp.previous = null; 
  497. 	                temp.next = null; 
  498. 	            }else { 
  499. 	                next.previous = null; 
  500. 	                next = null; 
  501. 	            } 
  502. 	            //更新父节点的关键字列表
  503. 	            parent.entries.remove(parent.children.indexOf(this));
  504.                 if((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
  505.                 			&& parent.children.size() >= 2))
  506.                 			||parent.isRoot && parent.children.size() >= 2){
  507. 	                 return returnValue;
  508. 				}
  509. 	            parent.updateRemove(tree);
  510.                 return returnValue;
  511. 	        } 
  512.         }
  513.         /*如果不是叶子节点*/
  514.         
  515.         //如果key小于等于节点最左边的key，沿第一个子节点继续搜索 
  516.         if (key.compareTo(entries.get(0).getKey()) < 0) { 
  517.             return children.get(0).remove(key, tree); 
  518.         //如果key大于节点最右边的key，沿最后一个子节点继续搜索 
  519.         }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { 
  520.             return children.get(children.size()-1).remove(key, tree); 
  521.         //否则沿比key大的前一个子节点继续搜索 
  522.         }else { 
  523.             int low = 0, high = entries.size() - 1, mid= 0;
  524.             int comp ;
  525.         		while (low <= high) {
  526.         			mid = (low + high) / 2;
  527.         			comp = entries.get(mid).getKey().compareTo(key);
  528.         			if (comp == 0) {
  529.         				return children.get(mid + 1).remove(key, tree); 
  530.         			} else if (comp < 0) {
  531.         				low = mid + 1;
  532.         			} else {
  533.         				high = mid - 1;
  534.         			}
  535.         		}
  536.         		return children.get(low).remove(key, tree); 
  537.         } 
  538.     } 
  539.      
  540.     /** 判断当前节点是否包含该关键字*/ 
  541.     protected int contains(K key) { 
  542.     		int low = 0, high = entries.size() - 1, mid;
  543.         int comp ;
  544. 		while (low <= high) {
  545. 			mid = (low + high) / 2;
  546. 			comp = entries.get(mid).getKey().compareTo(key);
  547. 			if (comp == 0) {
  548. 				return mid;
  549. 			} else if (comp < 0) {
  550. 				low = mid + 1;
  551. 			} else {
  552. 				high = mid - 1;
  553. 			}
  554. 		}
  555. 		return -1;
  556.     } 
  557.      
  558.     /** 插入到当前节点的关键字中*/ 
  559.     protected void insertOrUpdate(K key, V value){ 
  560.     		//二叉查找，插入
  561.         int low = 0, high = entries.size() - 1, mid;
  562.         int comp ;
  563. 		while (low <= high) {
  564. 			mid = (low + high) / 2;
  565. 			comp = entries.get(mid).getKey().compareTo(key);
  566. 			if (comp == 0) {
  567. 				entries.get(mid).setValue(value); 
  568. 				break;
  569. 			} else if (comp < 0) {
  570. 				low = mid + 1;
  571. 			} else {
  572. 				high = mid - 1;
  573. 			}
  574. 		}
  575. 		if(low>high){
  576. 			entries.add(low, new SimpleEntry<K, V>(key, value));
  577. 		}
  578.     } 
  579.      
  580.     /** 删除节点*/ 
  581.     protected V remove(K key){ 
  582.     		int low = 0,high = entries.size() -1,mid;
  583.     		int comp;
  584.     		while(low<= high){
  585.     			mid  = (low+high)/2;
  586.     			comp = entries.get(mid).getKey().compareTo(key);
  587.     			if(comp == 0){
  588.     				return entries.remove(mid).getValue();
  589.     			}else if(comp < 0){
  590. 				low = mid + 1;
  591. 			}else {
  592. 				high = mid - 1;
  593. 			}
  594.     		}
  595.         return null;
  596.     }   
  597.     public String toString(){ 
  598.         StringBuilder sb = new StringBuilder(); 
  599.         sb.append("isRoot: "); 
  600.         sb.append(isRoot); 
  601.         sb.append(", "); 
  602.         sb.append("isLeaf: "); 
  603.         sb.append(isLeaf); 
  604.         sb.append(", "); 
  605.         sb.append("keys: "); 
  606.         for (Entry<K,V> entry : entries){ 
  607.             sb.append(entry.getKey()); 
  608.             sb.append(", "); 
  609.         } 
  610.         sb.append(", "); 
  611.         return sb.toString(); 
  612.          
  613.     } 
  614.  
  615. }



声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/1007038
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号