基于Java实现的MySQL数据库.zip

package world.hzq.easysql.storage.engine.datastruct; import java.util.*; public class BPlusTree<K extends Comparable<K>, E> { private final int KEY_UPPER_BOUND; private final int UNDERFLOW_BOUND; private BPlusTreeNode root; public BPlusTree(int order) { this.KEY_UPPER_BOUND = order - 1; this.UNDERFLOW_BOUND = KEY_UPPER_BOUND / 2; } public BPlusTree() { this.KEY_UPPER_BOUND = 8; this.UNDERFLOW_BOUND = KEY_UPPER_BOUND / 2; } public void insert(K entry, E value) { if (root == null) { root = new BPlusTreeLeafNode(asList(entry), asList(asSet(value))); return; } BPlusTreeNode newChildNode = root.insert(entry, value); if (newChildNode != null) { K newRootEntry = newChildNode.getClass().equals(BPlusTreeLeafNode.class) ? newChildNode.entries.get(0) : ((BPlusTreeNonLeafNode) newChildNode).findLeafEntry(newChildNode); root = new BPlusTreeNonLeafNode(asList(newRootEntry), asList(root, newChildNode)); } } public E query(K entry) { if (root == null) { return null; } return root.query(entry); } public List<E> rangeQuery(K startInclude, K endExclude) { if (root == null) { return Collections.emptyList(); } return root.rangeQuery(startInclude, endExclude); } public boolean update(K entry, E oldValue, E newValue) { return root != null && root.update(entry, oldValue, newValue); } public boolean remove(K entry, E value) { if (root == null) { return false; } RemoveResult removeResult = root.remove(entry, value); if (!removeResult.isRemoved) { return false; } if (root.entries.isEmpty()) { this.handleRootUnderflow(); } return true; } public boolean remove(K entry) { if (root == null) { return false; } RemoveResult removeResult = root.remove(entry); if (!removeResult.isRemoved) { return false; } if (root.entries.isEmpty()) { this.handleRootUnderflow(); } return true; } private void handleRootUnderflow() { root = root.getClass().equals(BPlusTreeLeafNode.class) ? null : ((BPlusTreeNonLeafNode) root).children.get(0); } @SafeVarargs private final <T> List<T> asList(T... e) { List<T> res = new ArrayList<>(); Collections.addAll(res, e); return res; } @SafeVarargs private final <T> Set<T> asSet(T... e) { Set<T> res = new HashSet<>(); Collections.addAll(res, e); return res; } @Override public String toString() { return root.toString(); } private abstract class BPlusTreeNode { protected List<K> entries; protected boolean isFull() { return entries.size() == KEY_UPPER_BOUND; } protected boolean isUnderflow() { return entries.size() < UNDERFLOW_BOUND; } protected int getMedianIndex() { return KEY_UPPER_BOUND / 2; } protected int findEntryIndex(K entry) { int l = 0; int r = entries.size() - 1; int index = entries.size(); while (l <= r) { int mid = l + ((r - l) >> 1); if (entries.get(mid).compareTo(entry) >= 0) { index = mid; r = mid - 1; } else { l = mid + 1; } } return index; } public abstract List<E> rangeQuery(K startInclude, K endExclude); public abstract E query(K entry); public abstract BPlusTreeNode insert(K entry, E value); public abstract boolean update(K entry, E oldValue, E newValue); public abstract RemoveResult remove(K entry); public abstract RemoveResult remove(K entry, E value); public abstract void combine(BPlusTreeNode neighbor, K parentEntry); public abstract void borrow(BPlusTreeNode neighbor, K parentEntry, boolean isLeft); } private class BPlusTreeNonLeafNode extends BPlusTreeNode { public List<BPlusTreeNode> children; public BPlusTreeNonLeafNode(List<K> entries, List<BPlusTreeNode> children) { this.entries = entries; this.children = children; } @Override public List<E> rangeQuery(K startInclude, K endExclude) { return children.get(findChildIndex(findEntryIndex(startInclude), startInclude)).rangeQuery(startInclude, endExclude); } @Override public E query(K entry) { return children.get(findChildIndex(findEntryIndex(entry), entry)).query(entry); } @Override public boolean update(K entry, E oldValue, E newValue) { return children.get(findChildIndex(findEntryIndex(entry), entry)).update(entry, oldValue, newValue); } @Override public BPlusTreeNode insert(K entry, E value) { BPlusTreeNode newChildNode = children.get(findChildIndex(findEntryIndex(entry), entry)).insert(entry, value); if (newChildNode != null) { K newEntry = findLeafEntry(newChildNode); int newEntryIndex = findEntryIndex(newEntry); if (isFull()) { BPlusTreeNonLeafNode newNonLeafNode = split(); int medianIndex = getMedianIndex(); if (newEntryIndex < medianIndex) { entries.add(newEntryIndex, newEntry); children.add(newEntryIndex + 1, newChildNode); } else { int rightIndex = newNonLeafNode.findEntryIndex(newEntry); newNonLeafNode.entries.add(rightIndex, newEntry); newNonLeafNode.children.add(rightIndex, newChildNode); } newNonLeafNode.entries.remove(0); return newNonLeafNode; } entries.add(newEntryIndex, newEntry); children.add(newEntryIndex + 1, newChildNode); } return null; } @Override public RemoveResult remove(K entry) { int entryIndex = findEntryIndex(entry); int childIndex = findChildIndex(entryIndex, entry); BPlusTreeNode childNode = children.get(childIndex); RemoveResult removeResult = childNode.remove(entry); if (!removeResult.isRemoved) { return removeResult; } if (removeResult.isUnderflow) { this.handleUnderflow(childNode, childIndex, entryIndex); } return new RemoveResult(true, isUnderflow()); } @Override public RemoveResult remove(K entry, E value) { int entryIndex = findEntryIndex(entry); int childIndex = findChildIndex(entryIndex, entry); BPlusTreeNode childNode = children.get(childIndex); RemoveResult removeResult = childNode.remove(entry, value); if (!removeResult.isRemoved) { return removeResult; } if (removeResult.isUnderflow) { this.handleUnderflow(childNode, childIndex, entryIndex); } return new RemoveResult(true, isUnderflow()); } @Override public void combine(BPlusTreeNode neighbor, K parentEntry) { BPlusTreeNonLeafNode nonLeafNode = (BPlusTreeNonLeafNode) neighbor; this.entries.add(parentEntry); this.entries.addAll(nonLeafNode.entries); this.children.addAll(nonLeafNode.children); } @O