如何实现并使用Java中的B树数据结构？
- 内容介绍
- 文章标签
- 相关推荐
本文共计3599个文字，预计阅读时间需要15分钟。
javapackage cn.nudt681.nssas.core.analysis.btree;
import java.util.ArrayList;import java.util.List;import java.util.Map.Entry;
public class BPTreeNode { /** 是否为叶子节点 */ protected boolean isLeaf;}
BPTreeNodepackage cn.nudt681.nssas.core.analysis.btree;
import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
public class BPTreeNode {
/**
* 是否为叶子节点
*/
protected boolean isLeaf;
/**
* 是否为根节点
*/
protected boolean isRoot;
/**
* 父节点
*/
protected BPTreeNode parent;
/**
* 叶节点的前节点
*/
protected BPTreeNode previous;
/**
* 叶节点的后节点
*/
protected BPTreeNode next;
/**
* 节点的关键字
*/
protected List
package cn.nudt681.nssas.core.analysis.btree;
public interface BPTreeOperations {
/**
* 查询
* @param key
* @return
*/
Object get(Comparable
package cn.nudt681.nssas.core.analysis.btree;
/**
* B+树工具类
*/
public class BPTreeTemplate implements BPTreeOperations {
/**
* 根节点
*/
protected BPTreeNode root;
/**
* 阶数，M值
*/
protected int order;
/**
* 叶子节点的链表头
*/
protected BPTreeNode head;
public BPTreeNode getHead() {
return head;
}
public void setHead(BPTreeNode head) {
this.head = head;
}
public BPTreeNode getRoot() {
return root;
}
public void setRoot(BPTreeNode root) {
this.root = root;
}
public int getOrder() {
return order;
}
public void setOrder(int order) {
this.order = order;
}
public BPTreeTemplate(int order) {
if (order < 3) {
System.out.print("order must be greater than 2");
System.exit(0);
}
this.order = order;
root = new BPTreeNode(true, true);
head = root;
}
@Override
public void insertOrUpdate(Comparable
package cn.nudt681.nssas.core.analysis.btree;
import cn.nudt681.nssas.model.Event;
import java.sql.SQLException;
import java.util.List;
/**
* Created by xuliugen on 2017/9/18.
*/
public class BPTreeBuilder {
/**
* 将记录添加到B+树
* @param treeTemplate
* @throws Exception
*/
public static void buildRecords(BPTreeTemplate treeTemplate) throws Exception {
List
package cn.nudt681.nssas.core.analysis.btree; import org.junit.Test; import java.util.Scanner; public class TestApplication { @Test public void testBatchSearch() { BPTreeTemplate treeTemplate = new BPTreeTemplate(6); try { BPTreeBuilder.buildRecords(treeTemplate); } catch (Exception e) { e.printStackTrace(); } long startSearchTime = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { treeTemplate.get(342755l); } long endSearchTime = System.currentTimeMillis(); System.out.println("Caused Time:" + (endSearchTime - startSearchTime) + "ms"); } public static void main(String[] args) { BPTreeTemplate treeTemplate = new BPTreeTemplate(6); try { BPTreeBuilder.buildRecords(treeTemplate); } catch (Exception e) { e.printStackTrace(); } boolean exit = false; while (!exit) { System.out.println("***************************************"); System.out.println("** 1.Search By Value; ***"); System.out.println("** 2.Insert A Value; ***"); System.out.println("** 3.Delete A Value; ***"); System.out.println("** 4.Exit The System. ***"); System.out.println("***************************************"); int choice = 0; Scanner scanner = new Scanner(System.in); choice = scanner.nextInt(); long key; Object object; switch (choice) { case 1: System.out.println("Input the key: "); key = scanner.nextLong(); long startSearchTime = System.nanoTime(); object = treeTemplate.get(key); long endSearchTime = System.nanoTime(); if (object == null) { System.out.println("Tere is no key for " + key); } else { System.out.println("Searching successfully！ Caused Time:" + (endSearchTime - startSearchTime) + "ns! The data:" + object.toString()); } break; case 2: System.out.println("Input the key: "); key = scanner.nextInt(); treeTemplate.insertOrUpdate(key, key); System.out.println("Insert successfully"); break; case 3: System.out.println("Input the key: "); key = scanner.nextInt(); if (treeTemplate.remove(key)) { System.out.println("Delete successfully"); } else { System.out.println("There is no key of " + key + " to delete"); } break; case 4: exit = true; break; default: break; } } } } Event
package cn.nudt681.nssas.model; /** * 事件 * Created by xuliugen on 2017/9/26. */ public class Event { /** * 事件ID，32位UUID */ private String eventId; /** * 源IP地址，11位无符号位存储 */ private Integer srcIp; /** * 目标IP地址，11位无符号位存储 */ private Integer tarIp; /** * 源端口 */ private Integer srcPort; private Integer collectorId; /** * 目的端口 */ private Integer tarPort; /** * 设备ID */ private Long pluginId; /** * */ private Long pluginSid; /** * 源IP地址区域 */ private String srcArea; /** * 目标IP地址区域 */ private String tarArea; /** * 源IP地址区域城市 */ private String srcCity; /** * 目标IP地址城市 */ private String tarCity; /** * 事件生成时间 */ private String time; public String getEventId() { return eventId; } public void setEventId(String eventId) { this.eventId = eventId; } public Integer getSrcIp() { return srcIp; } public void setSrcIp(Integer srcIp) { this.srcIp = srcIp; } public Integer getTarIp() { return tarIp; } public void setTarIp(Integer tarIp) { this.tarIp = tarIp; } public Integer getSrcPort() { return srcPort; } public void setSrcPort(Integer srcPort) { this.srcPort = srcPort; } public Integer getTarPort() { return tarPort; } public void setTarPort(Integer tarPort) { this.tarPort = tarPort; } public Long getPluginId() { return pluginId; } public void setPluginId(Long pluginId) { this.pluginId = pluginId; } public Long getPluginSid() { return pluginSid; } public void setPluginSid(Long pluginSid) { this.pluginSid = pluginSid; } public String getSrcArea() { return srcArea; } public void setSrcArea(String srcArea) { this.srcArea = srcArea; } public String getTarArea() { return tarArea; } public void setTarArea(String tarArea) { this.tarArea = tarArea; } public String getTime() { return time; } public void setTime(String time) { this.time = time; } public Integer getCollectorId() { return collectorId; } public void setCollectorId(Integer collectorId) { this.collectorId = collectorId; } public String getSrcCity() { return srcCity; } public void setSrcCity(String srcCity) { this.srcCity = srcCity; } public String getTarCity() { return tarCity; } public void setTarCity(String tarCity) { this.tarCity = tarCity; } }
本文共计3599个文字，预计阅读时间需要15分钟。
javapackage cn.nudt681.nssas.core.analysis.btree;
import java.util.ArrayList;import java.util.List;import java.util.Map.Entry;
public class BPTreeNode { /** 是否为叶子节点 */ protected boolean isLeaf;}
BPTreeNodepackage cn.nudt681.nssas.core.analysis.btree;
import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
public class BPTreeNode {
/**
* 是否为叶子节点
*/
protected boolean isLeaf;
/**
* 是否为根节点
*/
protected boolean isRoot;
/**
* 父节点
*/
protected BPTreeNode parent;
/**
* 叶节点的前节点
*/
protected BPTreeNode previous;
/**
* 叶节点的后节点
*/
protected BPTreeNode next;
/**
* 节点的关键字
*/
protected List
package cn.nudt681.nssas.core.analysis.btree;
public interface BPTreeOperations {
/**
* 查询
* @param key
* @return
*/
Object get(Comparable
package cn.nudt681.nssas.core.analysis.btree;
/**
* B+树工具类
*/
public class BPTreeTemplate implements BPTreeOperations {
/**
* 根节点
*/
protected BPTreeNode root;
/**
* 阶数，M值
*/
protected int order;
/**
* 叶子节点的链表头
*/
protected BPTreeNode head;
public BPTreeNode getHead() {
return head;
}
public void setHead(BPTreeNode head) {
this.head = head;
}
public BPTreeNode getRoot() {
return root;
}
public void setRoot(BPTreeNode root) {
this.root = root;
}
public int getOrder() {
return order;
}
public void setOrder(int order) {
this.order = order;
}
public BPTreeTemplate(int order) {
if (order < 3) {
System.out.print("order must be greater than 2");
System.exit(0);
}
this.order = order;
root = new BPTreeNode(true, true);
head = root;
}
@Override
public void insertOrUpdate(Comparable
package cn.nudt681.nssas.core.analysis.btree;
import cn.nudt681.nssas.model.Event;
import java.sql.SQLException;
import java.util.List;
/**
* Created by xuliugen on 2017/9/18.
*/
public class BPTreeBuilder {
/**
* 将记录添加到B+树
* @param treeTemplate
* @throws Exception
*/
public static void buildRecords(BPTreeTemplate treeTemplate) throws Exception {
List
package cn.nudt681.nssas.core.analysis.btree; import org.junit.Test; import java.util.Scanner; public class TestApplication { @Test public void testBatchSearch() { BPTreeTemplate treeTemplate = new BPTreeTemplate(6); try { BPTreeBuilder.buildRecords(treeTemplate); } catch (Exception e) { e.printStackTrace(); } long startSearchTime = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { treeTemplate.get(342755l); } long endSearchTime = System.currentTimeMillis(); System.out.println("Caused Time:" + (endSearchTime - startSearchTime) + "ms"); } public static void main(String[] args) { BPTreeTemplate treeTemplate = new BPTreeTemplate(6); try { BPTreeBuilder.buildRecords(treeTemplate); } catch (Exception e) { e.printStackTrace(); } boolean exit = false; while (!exit) { System.out.println("***************************************"); System.out.println("** 1.Search By Value; ***"); System.out.println("** 2.Insert A Value; ***"); System.out.println("** 3.Delete A Value; ***"); System.out.println("** 4.Exit The System. ***"); System.out.println("***************************************"); int choice = 0; Scanner scanner = new Scanner(System.in); choice = scanner.nextInt(); long key; Object object; switch (choice) { case 1: System.out.println("Input the key: "); key = scanner.nextLong(); long startSearchTime = System.nanoTime(); object = treeTemplate.get(key); long endSearchTime = System.nanoTime(); if (object == null) { System.out.println("Tere is no key for " + key); } else { System.out.println("Searching successfully！ Caused Time:" + (endSearchTime - startSearchTime) + "ns! The data:" + object.toString()); } break; case 2: System.out.println("Input the key: "); key = scanner.nextInt(); treeTemplate.insertOrUpdate(key, key); System.out.println("Insert successfully"); break; case 3: System.out.println("Input the key: "); key = scanner.nextInt(); if (treeTemplate.remove(key)) { System.out.println("Delete successfully"); } else { System.out.println("There is no key of " + key + " to delete"); } break; case 4: exit = true; break; default: break; } } } } Event
package cn.nudt681.nssas.model; /** * 事件 * Created by xuliugen on 2017/9/26. */ public class Event { /** * 事件ID，32位UUID */ private String eventId; /** * 源IP地址，11位无符号位存储 */ private Integer srcIp; /** * 目标IP地址，11位无符号位存储 */ private Integer tarIp; /** * 源端口 */ private Integer srcPort; private Integer collectorId; /** * 目的端口 */ private Integer tarPort; /** * 设备ID */ private Long pluginId; /** * */ private Long pluginSid; /** * 源IP地址区域 */ private String srcArea; /** * 目标IP地址区域 */ private String tarArea; /** * 源IP地址区域城市 */ private String srcCity; /** * 目标IP地址城市 */ private String tarCity; /** * 事件生成时间 */ private String time; public String getEventId() { return eventId; } public void setEventId(String eventId) { this.eventId = eventId; } public Integer getSrcIp() { return srcIp; } public void setSrcIp(Integer srcIp) { this.srcIp = srcIp; } public Integer getTarIp() { return tarIp; } public void setTarIp(Integer tarIp) { this.tarIp = tarIp; } public Integer getSrcPort() { return srcPort; } public void setSrcPort(Integer srcPort) { this.srcPort = srcPort; } public Integer getTarPort() { return tarPort; } public void setTarPort(Integer tarPort) { this.tarPort = tarPort; } public Long getPluginId() { return pluginId; } public void setPluginId(Long pluginId) { this.pluginId = pluginId; } public Long getPluginSid() { return pluginSid; } public void setPluginSid(Long pluginSid) { this.pluginSid = pluginSid; } public String getSrcArea() { return srcArea; } public void setSrcArea(String srcArea) { this.srcArea = srcArea; } public String getTarArea() { return tarArea; } public void setTarArea(String tarArea) { this.tarArea = tarArea; } public String getTime() { return time; } public void setTime(String time) { this.time = time; } public Integer getCollectorId() { return collectorId; } public void setCollectorId(Integer collectorId) { this.collectorId = collectorId; } public String getSrcCity() { return srcCity; } public void setSrcCity(String srcCity) { this.srcCity = srcCity; } public String getTarCity() { return tarCity; } public void setTarCity(String tarCity) { this.tarCity = tarCity; } }