- 浏览: 73016 次
- 性别:
- 来自: 杭州
最新评论
-
zhaojian770627:
...
B+树的Java实现 -
kevindude:
包含在了clyde库里
Clyde学习笔记三(Config) -
silverys:
能否提供demo下载学习一下,谢谢
3D MMO Demo -
silverys:
请问下,这个Three Rings Resource Edit ...
Clyde学习笔记三(Config) -
Bactryki:
要用什么包呢?
基于Struts2+Spring+iBatis的web应用最佳实践系列之二(访问控制篇上)
B+树的定义:
1.任意非叶子结点最多有M个子节点;且M>2;
2.除根结点以外的非叶子结点至少有 M/2个子节点;
3.根结点至少有2个子节点;
4.除根节点外每个结点存放至少M/2和至多M个关键字;(至少2个关键字)
5.非叶子结点的子树指针与关键字个数相同;
6.所有结点的关键字:K[1], K[2], …, K[M];且K[i] < K[i+1];
7.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树;
8.所有叶子结点位于同一层;
5.为所有叶子结点增加一个链指针;
6.所有关键字都在叶子结点出现;
Java实现:
接口:
package com.meidusa.test; public interface B { public Object get(Comparable key); //查询 public void remove(Comparable key); //移除 public void insertOrUpdate(Comparable key, Object obj); //插入或者更新,如果已经存在,就更新,否则插入 }
B+树:
package com.meidusa.test; import java.util.Random; public class BplusTree implements B { /** 根节点 */ protected Node root; /** 阶数,M值 */ protected int order; /** 叶子节点的链表头*/ protected Node head; public Node getHead() { return head; } public void setHead(Node head) { this.head = head; } public Node getRoot() { return root; } public void setRoot(Node root) { this.root = root; } public int getOrder() { return order; } public void setOrder(int order) { this.order = order; } @Override public Object get(Comparable key) { return root.get(key); } @Override public void remove(Comparable key) { root.remove(key, this); } @Override public void insertOrUpdate(Comparable key, Object obj) { root.insertOrUpdate(key, obj, this); } public BplusTree(int order){ if (order < 3) { System.out.print("order must be greater than 2"); System.exit(0); } this.order = order; root = new Node(true, true); head = root; } //测试 public static void main(String[] args) { BplusTree tree = new BplusTree(6); Random random = new Random(); long current = System.currentTimeMillis(); for (int j = 0; j < 100000; j++) { for (int i = 0; i < 100; i++) { int randomNumber = random.nextInt(1000); tree.insertOrUpdate(randomNumber, randomNumber); } for (int i = 0; i < 100; i++) { int randomNumber = random.nextInt(1000); tree.remove(randomNumber); } } long duration = System.currentTimeMillis() - current; System.out.println("time elpsed for duration: " + duration); int search = 80; System.out.print(tree.get(search)); } }
节点:
package com.meidusa.test; import java.util.AbstractMap.SimpleEntry; import java.util.ArrayList; import java.util.List; import java.util.Map.Entry; public class Node { /** 是否为叶子节点 */ protected boolean isLeaf; /** 是否为根节点*/ protected boolean isRoot; /** 父节点 */ protected Node parent; /** 叶节点的前节点*/ protected Node previous; /** 叶节点的后节点*/ protected Node next; /** 节点的关键字 */ protected List<Entry<Comparable, Object>> entries; /** 子节点 */ protected List<Node> children; public Node(boolean isLeaf) { this.isLeaf = isLeaf; entries = new ArrayList<Entry<Comparable, Object>>(); if (!isLeaf) { children = new ArrayList<Node>(); } } public Node(boolean isLeaf, boolean isRoot) { this(isLeaf); this.isRoot = isRoot; } public Object get(Comparable key) { //如果是叶子节点 if (isLeaf) { for (Entry<Comparable, Object> entry : entries) { if (entry.getKey().compareTo(key) == 0) { //返回找到的对象 return entry.getValue(); } } //未找到所要查询的对象 return null; //如果不是叶子节点 }else { //如果key小于等于节点最左边的key,沿第一个子节点继续搜索 if (key.compareTo(entries.get(0).getKey()) <= 0) { return children.get(0).get(key); //如果key大于节点最右边的key,沿最后一个子节点继续搜索 }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { return children.get(children.size()-1).get(key); //否则沿比key大的前一个子节点继续搜索 }else { for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) { return children.get(i).get(key); } } } } return null; } public void insertOrUpdate(Comparable key, Object obj, BplusTree tree){ //如果是叶子节点 if (isLeaf){ //不需要分裂,直接插入或更新 if (contains(key) || entries.size() < tree.getOrder()){ insertOrUpdate(key, obj); if (parent != null) { //更新父节点 parent.updateInsert(tree); } //需要分裂 }else { //分裂成左右两个节点 Node left = new Node(true); Node right = new Node(true); //设置链接 if (previous != null){ previous.setNext(left); left.setPrevious(previous); } if (next != null) { next.setPrevious(right); right.setNext(next); } if (previous == null){ tree.setHead(left); } left.setNext(right); right.setPrevious(left); previous = null; next = null; //左右两个节点关键字长度 int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2; int rightSize = (tree.getOrder() + 1) / 2; //复制原节点关键字到分裂出来的新节点 insertOrUpdate(key, obj); for (int i = 0; i < leftSize; i++){ left.getEntries().add(entries.get(i)); } for (int i = 0; i < rightSize; i++){ right.getEntries().add(entries.get(leftSize + i)); } //如果不是根节点 if (parent != null) { //调整父子节点关系 int index = parent.getChildren().indexOf(this); parent.getChildren().remove(this); left.setParent(parent); right.setParent(parent); parent.getChildren().add(index,left); parent.getChildren().add(index + 1, right); setEntries(null); setChildren(null); //父节点插入或更新关键字 parent.updateInsert(tree); setParent(null); //如果是根节点 }else { isRoot = false; Node parent = new Node(false, true); tree.setRoot(parent); left.setParent(parent); right.setParent(parent); parent.getChildren().add(left); parent.getChildren().add(right); setEntries(null); setChildren(null); //更新根节点 parent.updateInsert(tree); } } //如果不是叶子节点 }else { //如果key小于等于节点最左边的key,沿第一个子节点继续搜索 if (key.compareTo(entries.get(0).getKey()) <= 0) { children.get(0).insertOrUpdate(key, obj, tree); //如果key大于节点最右边的key,沿最后一个子节点继续搜索 }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { children.get(children.size()-1).insertOrUpdate(key, obj, tree); //否则沿比key大的前一个子节点继续搜索 }else { for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) { children.get(i).insertOrUpdate(key, obj, tree); break; } } } } } /** 插入节点后中间节点的更新 */ protected void updateInsert(BplusTree tree){ validate(this, tree); //如果子节点数超出阶数,则需要分裂该节点 if (children.size() > tree.getOrder()) { //分裂成左右两个节点 Node left = new Node(false); Node right = new Node(false); //左右两个节点关键字长度 int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2; int rightSize = (tree.getOrder() + 1) / 2; //复制子节点到分裂出来的新节点,并更新关键字 for (int i = 0; i < leftSize; i++){ left.getChildren().add(children.get(i)); left.getEntries().add(new SimpleEntry(children.get(i).getEntries().get(0).getKey(), null)); children.get(i).setParent(left); } for (int i = 0; i < rightSize; i++){ right.getChildren().add(children.get(leftSize + i)); right.getEntries().add(new SimpleEntry(children.get(leftSize + i).getEntries().get(0).getKey(), null)); children.get(leftSize + i).setParent(right); } //如果不是根节点 if (parent != null) { //调整父子节点关系 int index = parent.getChildren().indexOf(this); parent.getChildren().remove(this); left.setParent(parent); right.setParent(parent); parent.getChildren().add(index,left); parent.getChildren().add(index + 1, right); setEntries(null); setChildren(null); //父节点更新关键字 parent.updateInsert(tree); setParent(null); //如果是根节点 }else { isRoot = false; Node parent = new Node(false, true); tree.setRoot(parent); left.setParent(parent); right.setParent(parent); parent.getChildren().add(left); parent.getChildren().add(right); setEntries(null); setChildren(null); //更新根节点 parent.updateInsert(tree); } } } /** 调整节点关键字*/ protected static void validate(Node node, BplusTree tree) { // 如果关键字个数与子节点个数相同 if (node.getEntries().size() == node.getChildren().size()) { for (int i = 0; i < node.getEntries().size(); i++) { Comparable key = node.getChildren().get(i).getEntries().get(0).getKey(); if (node.getEntries().get(i).getKey().compareTo(key) != 0) { node.getEntries().remove(i); node.getEntries().add(i, new SimpleEntry(key, null)); if(!node.isRoot()){ validate(node.getParent(), tree); } } } // 如果子节点数不等于关键字个数但仍大于M / 2并且小于M,并且大于2 } else if (node.isRoot() && node.getChildren().size() >= 2 ||node.getChildren().size() >= tree.getOrder() / 2 && node.getChildren().size() <= tree.getOrder() && node.getChildren().size() >= 2) { node.getEntries().clear(); for (int i = 0; i < node.getChildren().size(); i++) { Comparable key = node.getChildren().get(i).getEntries().get(0).getKey(); node.getEntries().add(new SimpleEntry(key, null)); if (!node.isRoot()) { validate(node.getParent(), tree); } } } } /** 删除节点后中间节点的更新*/ protected void updateRemove(BplusTree tree) { validate(this, tree); // 如果子节点数小于M / 2或者小于2,则需要合并节点 if (children.size() < tree.getOrder() / 2 || children.size() < 2) { if (isRoot) { // 如果是根节点并且子节点数大于等于2,OK if (children.size() >= 2) { return; // 否则与子节点合并 } else { Node root = children.get(0); tree.setRoot(root); root.setParent(null); root.setRoot(true); setEntries(null); setChildren(null); } } else { //计算前后节点 int currIdx = parent.getChildren().indexOf(this); int prevIdx = currIdx - 1; int nextIdx = currIdx + 1; Node previous = null, next = null; if (prevIdx >= 0) { previous = parent.getChildren().get(prevIdx); } if (nextIdx < parent.getChildren().size()) { next = parent.getChildren().get(nextIdx); } // 如果前节点子节点数大于M / 2并且大于2,则从其处借补 if (previous != null && previous.getChildren().size() > tree.getOrder() / 2 && previous.getChildren().size() > 2) { //前叶子节点末尾节点添加到首位 int idx = previous.getChildren().size() - 1; Node borrow = previous.getChildren().get(idx); previous.getChildren().remove(idx); borrow.setParent(this); children.add(0, borrow); validate(previous, tree); validate(this, tree); parent.updateRemove(tree); // 如果后节点子节点数大于M / 2并且大于2,则从其处借补 } else if (next != null && next.getChildren().size() > tree.getOrder() / 2 && next.getChildren().size() > 2) { //后叶子节点首位添加到末尾 Node borrow = next.getChildren().get(0); next.getChildren().remove(0); borrow.setParent(this); children.add(borrow); validate(next, tree); validate(this, tree); parent.updateRemove(tree); // 否则需要合并节点 } else { // 同前面节点合并 if (previous != null && (previous.getChildren().size() <= tree.getOrder() / 2 || previous.getChildren().size() <= 2)) { for (int i = previous.getChildren().size() - 1; i >= 0; i--) { Node child = previous.getChildren().get(i); children.add(0, child); child.setParent(this); } previous.setChildren(null); previous.setEntries(null); previous.setParent(null); parent.getChildren().remove(previous); validate(this, tree); parent.updateRemove(tree); // 同后面节点合并 } else if (next != null && (next.getChildren().size() <= tree.getOrder() / 2 || next.getChildren().size() <= 2)) { for (int i = 0; i < next.getChildren().size(); i++) { Node child = next.getChildren().get(i); children.add(child); child.setParent(this); } next.setChildren(null); next.setEntries(null); next.setParent(null); parent.getChildren().remove(next); validate(this, tree); parent.updateRemove(tree); } } } } } public void remove(Comparable key, BplusTree tree){ //如果是叶子节点 if (isLeaf){ //如果不包含该关键字,则直接返回 if (!contains(key)){ return; } //如果既是叶子节点又是跟节点,直接删除 if (isRoot) { remove(key); }else { //如果关键字数大于M / 2,直接删除 if (entries.size() > tree.getOrder() / 2 && entries.size() > 2) { remove(key); }else { //如果自身关键字数小于M / 2,并且前节点关键字数大于M / 2,则从其处借补 if (previous != null && previous.getEntries().size() > tree.getOrder() / 2 && previous.getEntries().size() > 2 && previous.getParent() == parent) { int size = previous.getEntries().size(); Entry<Comparable, Object> entry = previous.getEntries().get(size - 1); previous.getEntries().remove(entry); //添加到首位 entries.add(0, entry); remove(key); //如果自身关键字数小于M / 2,并且后节点关键字数大于M / 2,则从其处借补 }else if (next != null && next.getEntries().size() > tree.getOrder() / 2 && next.getEntries().size() > 2 && next.getParent() == parent) { Entry<Comparable, Object> entry = next.getEntries().get(0); next.getEntries().remove(entry); //添加到末尾 entries.add(entry); remove(key); //否则需要合并叶子节点 }else { //同前面节点合并 if (previous != null && (previous.getEntries().size() <= tree.getOrder() / 2 || previous.getEntries().size() <= 2) && previous.getParent() == parent) { for (int i = previous.getEntries().size() - 1; i >=0; i--) { //从末尾开始添加到首位 entries.add(0, previous.getEntries().get(i)); } remove(key); previous.setParent(null); previous.setEntries(null); parent.getChildren().remove(previous); //更新链表 if (previous.getPrevious() != null) { Node temp = previous; temp.getPrevious().setNext(this); previous = temp.getPrevious(); temp.setPrevious(null); temp.setNext(null); }else { tree.setHead(this); previous.setNext(null); previous = null; } //同后面节点合并 }else if(next != null && (next.getEntries().size() <= tree.getOrder() / 2 || next.getEntries().size() <= 2) && next.getParent() == parent){ for (int i = 0; i < next.getEntries().size(); i++) { //从首位开始添加到末尾 entries.add(next.getEntries().get(i)); } remove(key); next.setParent(null); next.setEntries(null); parent.getChildren().remove(next); //更新链表 if (next.getNext() != null) { Node temp = next; temp.getNext().setPrevious(this); next = temp.getNext(); temp.setPrevious(null); temp.setNext(null); }else { next.setPrevious(null); next = null; } } } } parent.updateRemove(tree); } //如果不是叶子节点 }else { //如果key小于等于节点最左边的key,沿第一个子节点继续搜索 if (key.compareTo(entries.get(0).getKey()) <= 0) { children.get(0).remove(key, tree); //如果key大于节点最右边的key,沿最后一个子节点继续搜索 }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { children.get(children.size()-1).remove(key, tree); //否则沿比key大的前一个子节点继续搜索 }else { for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) { children.get(i).remove(key, tree); break; } } } } } /** 判断当前节点是否包含该关键字*/ protected boolean contains(Comparable key) { for (Entry<Comparable, Object> entry : entries) { if (entry.getKey().compareTo(key) == 0) { return true; } } return false; } /** 插入到当前节点的关键字中*/ protected void insertOrUpdate(Comparable key, Object obj){ Entry<Comparable, Object> entry = new SimpleEntry<Comparable, Object>(key, obj); //如果关键字列表长度为0,则直接插入 if (entries.size() == 0) { entries.add(entry); return; } //否则遍历列表 for (int i = 0; i < entries.size(); i++) { //如果该关键字键值已存在,则更新 if (entries.get(i).getKey().compareTo(key) == 0) { entries.get(i).setValue(obj); return; //否则插入 }else if (entries.get(i).getKey().compareTo(key) > 0){ //插入到链首 if (i == 0) { entries.add(0, entry); return; //插入到中间 }else { entries.add(i, entry); return; } } } //插入到末尾 entries.add(entries.size(), entry); } /** 删除节点*/ protected void remove(Comparable key){ int index = -1; for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) == 0) { index = i; break; } } if (index != -1) { entries.remove(index); } } public Node getPrevious() { return previous; } public void setPrevious(Node previous) { this.previous = previous; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public boolean isLeaf() { return isLeaf; } public void setLeaf(boolean isLeaf) { this.isLeaf = isLeaf; } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } public List<Entry<Comparable, Object>> getEntries() { return entries; } public void setEntries(List<Entry<Comparable, Object>> entries) { this.entries = entries; } public List<Node> getChildren() { return children; } public void setChildren(List<Node> children) { this.children = children; } public boolean isRoot() { return isRoot; } public void setRoot(boolean isRoot) { this.isRoot = isRoot; } public String toString(){ StringBuilder sb = new StringBuilder(); sb.append("isRoot: "); sb.append(isRoot); sb.append(", "); sb.append("isLeaf: "); sb.append(isLeaf); sb.append(", "); sb.append("keys: "); for (Entry entry : entries){ sb.append(entry.getKey()); sb.append(", "); } sb.append(", "); return sb.toString(); } }
相关推荐
步骤为数据库文件创建一个B+树索引: (1)生成数据文件, (2)为数据库文件的属性创建B+ 树文件。 (3)给定键值,通过B+树进行查找。同时比较与直接扫描表的性能差别。(利用B+树时可根据内存大小决定放置多少层次到...
总结来说,Java实现B+树涉及的主要知识点包括数据结构设计、树的平衡策略、节点操作(插入、删除、查找)以及链表的使用。理解并掌握B+树的原理和实现,对于提高Java程序员在大数据处理和数据库系统开发方面的技能...
本节将详细讲解如何使用Java实现B+树,包括其基本概念、节点结构、树的构建、插入操作以及遍历方法。 首先,B+树是一种多路搜索树,其特性在于所有数据都存储在叶子节点中,而非叶子节点仅作为索引使用。这使得所有...
下面将详细讨论如何用Java实现B+树。 首先,B+树的节点分为两种类型:内部节点(或索引节点)和叶子节点。内部节点存储键值,不存储数据,而叶子节点则同时存储键值和对应的数据。在Java实现中,我们通常会创建两个...
这个程序是swing版本的b+树的实现及演示,适合学些b+树实现方式的同学们,详细情况可以参考我的博文:http://blog.csdn.net/cdnight/article/details/10973281, 希望对大家有所帮助。
本研究主要探讨如何在Java编程语言中实现B+树算法,以理解其原理并应用到实际项目中。 B+树是一种自平衡的多路查找树,其特点包括以下几点: 1. **分层结构**:B+树具有层级关系,根节点位于最顶层,叶子节点位于...
总之,B+树算法的Java实现是一种技术挑战,它需要开发者具备对数据结构和算法的深入理解,以及对Java语言特性的熟悉。通过研究和实践,可以加深对B+树在数据库索引构建和文件系统管理中应用的理解,并能够开发出性能...
在数据库和文件系统中,索引是一种至关重要的数据结构,它极大地优化了数据检索的速度。在本主题中,我们将深入探讨B+树这种高效的索引结构,并...在Java环境下实现B+树,可以利用其特性优化各种数据密集型应用的性能。
Java实现B+树的过程中,我们需要理解其核心原理并转化为编程语言的逻辑。 首先,B+树的特点包括: 1. **所有叶子节点在同一层**:这确保了从根节点到任意一个叶子节点的路径长度相同,提高了查询效率。 2. **叶子...
在Java中实现B+树,可以用于创建高效的索引结构,例如在数据库中用于快速查找记录。jdbm-1.0这个JAR包可能包含了B+树的实现,可以方便开发者在自己的项目中使用。 接下来是哈希表,它是一种根据关键字(key)直接...
对于Java实现,可以利用Java集合框架中的接口,如List或Map,来简化数据结构的实现。例如,每个节点可以是一个HashMap,键是键值,值是子节点。而C++实现中,可以使用STL容器,如std::vector或std::map,作为节点的...
在B+树中,所有的键都存在于叶子节点中,而内部节点仅作为索引使用,这与B树有所不同。这样的设计使得所有数据的访问最终都会定位到叶子节点,确保了所有数据查找的路径长度一致,提高了搜索效率。同时,由于叶子...
`BPlusTree-master`这个压缩包很可能包含了完整的Java实现B+树的源代码,包括B+树节点类、搜索、插入、删除等核心功能的实现,以及可能的单元测试和示例用法。通过查看源码,我们可以学习到如何在实际项目中构建这样...
**Java实现**: 在Java中,可以使用对象和接口来表示B+树的节点和指针。例如,可以创建一个Node类,包含关键字数组、子节点数组以及指向相邻节点的指针。使用递归或迭代的方式来实现插入、删除和查找操作。Java的...
B+ Tree是一种自平衡的树数据结构,广泛应用于数据库和文件系统的索引存储。它的设计目标是为了在磁盘等慢速存储介质上高效地进行数据检索。以下是对B+ Tree进行详细解释的内容: ### 1. 结构特征 B+ Tree的特点...
在Java中实现B+树可以帮助我们理解其内部工作原理,并且可以用于自定义的数据库系统或者搜索算法。下面我们将详细探讨B+树的原理以及如何在Java中实现它。 首先,了解B+树的基本概念是必要的。B+树是一种多路搜索树...
- **代码实现**:项目可能包括用C++、Java或Python等语言实现B+树的数据结构,包括插入、删除和查找等操作的算法。 - **报告**:报告将详细解释B+树的理论基础,分析实现过程中的关键步骤,以及可能遇到的问题和...
本文主要讨论两种常见的存储引擎——MyISAM和InnoDB,它们在B+树索引实现上的差异。 首先,MyISAM是MySQL早期的默认存储引擎,它在索引方面采用B+树结构。对于主键索引,MyISAM的B+树叶节点存储的是数据记录的物理...
在计算机科学中,B树(B-tree)是一种自平衡的多路查找树,它的设计目的是为了优化磁盘或网络存储环境下的数据检索效率。...在Java中实现B树需要理解其数据结构特点,并适当地处理插入、查找和删除操作,确保树的平衡。
java语言纯手写的B+树,100%原创可查不会与网上有雷同,支持插入删除,已经用gpt测过大量用例通过。 需要的可以取走,包对的,注释写的很多,希望能帮到有需要的人。