BPTreeNode package 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
package 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
> entries;
/**
* 子节点
*/
protected List
children; public BPTreeNode(boolean isLeaf) { this.isLeaf = isLeaf; entries = new ArrayList
>(); if (!isLeaf) { children = new ArrayList
(); } } public BPTreeNode(boolean isLeaf, boolean isRoot) { this(isLeaf); this.isRoot = isRoot; } public Object get(Comparable key) { //如果是叶子节点 if (isLeaf) { for (Entry
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, BPTreeTemplate tree) { //如果是叶子节点 if (isLeaf) { //不需要分裂，直接插入或更新 if (contains(key) || entries.size() < tree.getOrder()) { insertOrUpdate(key, obj); if (parent != null) { //更新父节点 parent.updateInsert(tree); } //需要分裂 } else { //分裂成左右两个节点 BPTreeNode left = new BPTreeNode(true); BPTreeNode right = new BPTreeNode(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; BPTreeNode parent = new BPTreeNode(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(BPTreeTemplate tree) { validate(this, tree); //如果子节点数超出阶数，则需要分裂该节点 if (children.size() > tree.getOrder()) { //分裂成左右两个节点 BPTreeNode left = new BPTreeNode(false); BPTreeNode right = new BPTreeNode(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; BPTreeNode parent = new BPTreeNode(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(BPTreeNode node, BPTreeTemplate 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(BPTreeTemplate 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 { BPTreeNode 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; BPTreeNode 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; BPTreeNode 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) { //后叶子节点首位添加到末尾 BPTreeNode 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--) { BPTreeNode 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++) { BPTreeNode 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 boolean remove(Comparable key, BPTreeTemplate tree) { //如果是叶子节点 boolean foud = false; if (isLeaf) { //如果不包含该关键字，则直接返回 if (!contains(key)) { return false; } //如果既是叶子节点又是跟节点，直接删除 if (isRoot) { if (remove(key)) { foud = true; } } else { //如果关键字数大于M / 2，直接删除 if (entries.size() > tree.getOrder() / 2 && entries.size() > 2) { if (remove(key)) { foud = true; } } 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
entry = previous.getEntries().get(size - 1); previous.getEntries().remove(entry); //添加到首位 entries.add(0, entry); if (remove(key)) { foud = true; } //如果自身关键字数小于M / 2，并且后节点关键字数大于M / 2，则从其处借补 } else if (next != null && next.getEntries().size() > tree.getOrder() / 2 && next.getEntries().size() > 2 && next.getParent() == parent) { Entry
entry = next.getEntries().get(0); next.getEntries().remove(entry); //添加到末尾 entries.add(entry); if (remove(key)) { foud = true; } //否则需要合并叶子节点 } 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)); } if (remove(key)) { foud = true; } previous.setParent(null); previous.setEntries(null); parent.getChildren().remove(previous); //更新链表 if (previous.getPrevious() != null) { BPTreeNode 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)); } if (remove(key)) { foud = true; } next.setParent(null); next.setEntries(null); parent.getChildren().remove(next); //更新链表 if (next.getNext() != null) { BPTreeNode 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) { if (children.get(0).remove(key, tree)) { foud = true; } //如果key大于节点最右边的key，沿最后一个子节点继续搜索 } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) { if (children.get(children.size() - 1).remove(key, tree)) { foud = true; } //否则沿比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) { if (children.get(i).remove(key, tree)) { foud = true; } } } } } if (foud) { return true; } else { return false; } } /** * 判断当前节点是否包含该关键字 */ protected boolean contains(Comparable key) { for (Entry
entry : entries) { if (entry.getKey().compareTo(key) == 0) { return true; } } return false; } /** * 插入到当前节点的关键字中 */ protected void insertOrUpdate(Comparable key, Object obj) { Entry
entry = new SimpleEntry
(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 boolean remove(Comparable key) { int index = -1; boolean foud = false; for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) == 0) { index = i; foud = true; break; } } if (index != -1) { entries.remove(index); } if (foud) { return true; } else { return false; } } public BPTreeNode getPrevious() { return previous; } public void setPrevious(BPTreeNode previous) { this.previous = previous; } public BPTreeNode getNext() { return next; } public void setNext(BPTreeNode next) { this.next = next; } public boolean isLeaf() { return isLeaf; } public void setLeaf(boolean isLeaf) { this.isLeaf = isLeaf; } public BPTreeNode getParent() { return parent; } public void setParent(BPTreeNode parent) { this.parent = parent; } public List
> getEntries() { return entries; } public void setEntries(List
> entries) { this.entries = entries; } public List
getChildren() { return children; } public void setChildren(List
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(); } }
BPTreeOperations
package cn.nudt681.nssas.core.analysis.btree;
public interface BPTreeOperations {
/**
* 查询
* @param key
* @return
*/
Object get(Comparable
key);
/**
* 移除
* @param key
* @return
*/
boolean remove(Comparable
key); /** * 插入或者更新，如果已经存在，更新，否则插入 * @param key * @param obj */ void insertOrUpdate(Comparable
key, Object obj); }
BPTreeTemplate
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
key, Object obj) {
root.insertOrUpdate(key, obj, this);
}
@Override
public Object get(Comparable
key) { return root.get(key); } @Override public boolean remove(Comparable
key) { return root.remove(key, this); } }
BPTreeBuilder
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
eventList = select();
System.out.println("Start Building B+ Tree...");
long startTime = System.currentTimeMillis();
for (int i = 0; i < eventList.size(); i++) {
treeTemplate.insertOrUpdate(eventList.get(i).getPluginSid(), eventList.get(i));
}
System.out.println("End Building B+ Tree... Caused Time:" + (System.currentTimeMillis() - startTime) + "ms");
}
/**
* 注意构造的数据
* @return
* @throws SQLException
*/
public static List
select() throws SQLException { List
events = new ArrayList<>(); for (int i = 0; i < 100; i++) { Event event = new Event(); event.setCollectorId(i); event.setEventId(i + ""); event.setPluginId(new Long(i)); event.setPluginSid(new Long(i)); event.setSrcArea("BJ"); event.setSrcCity("SC"); event.setSrcIp(i); events.add(event); } return events; } }
TestApplication
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;
}
}