com.github.basking2.sdsai.dsds

Class BTree<K,STOREKEY,V>

java.lang.Object

com.github.basking2.sdsai.dsds.BTree<K,STOREKEY,V>

Type Parameters:

K - The user key type. See Map for its use.

STOREKEY - The storage key that K will be transformed in to. The NodeStore must be able to convert a K to a STOREKEY and must be able to generate a STOREKEY for storing internal nodes.

V - The user value type. Sett Map for its use.

All Implemented Interfaces:

java.util.Map<K,V>

public class BTree<K,STOREKEY,V>
extends java.lang.Object
implements java.util.Map<K,V>

A B-Tree that uses a NodeStore object to persist Nodes and user data to blob storage. This is tailored to NoSQL document / key-value systems.

There is no concurrency built into this object so edits to a BTree must be coordinated through a locking mechanism or some otherwise atomic service. Developers looking to add transactionality should consider implementing a NodeStore to collect and atomically batch-update edits.

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Constructor Summary

Constructors

Constructor and Description
BTree(K rootKey, NodeStore<K,STOREKEY,V> nodeStore)
BTree(K rootKey, NodeStore<K,STOREKEY,V> nodeStore, int minData) Attempt to retrieve the root node stored at the rootKey or, if none is found, construct a new empty root node with minData*2 as the size of the maxData value to the Node's constructors.

Method Summary

Modifier and Type	Method and Description
void	clear() Clears the datastructure by doing a depth-first node traversal to delete all the user data and the node data from the NodeStore.
boolean	containsKey(java.lang.Object key) Check the NodeStore for the given key.
boolean	containsValue(java.lang.Object value)
void	destroy() Whereas clearing will destroy all but the root node, this method calls clear() and deletes the root node key.
void	eachDepthFirst(NodeFunction<K,STOREKEY> callable) Recrusively depth-first execute NodeFunction.call(Node) on each.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet()
boolean	equals(java.lang.Object o)
V	get(java.lang.Object key) Retrieve the object from the NodeStore.
BTreeLocation<K,STOREKEY>	getEnd()
NodeLocation<K,STOREKEY>	getEndNode()
java.util.Iterator<K>	getIterator() Return a BTreeLocation wrapped in an iterator.
BTreeLocation<K,STOREKEY>	getLocation(K key)
java.util.Iterator<Node<K,STOREKEY>>	getNodeIterator()
java.util.Iterator<K>	getReverseIterator() Return a BTreeLocation wrapped in an iterator.
java.util.Iterator<Node<K,STOREKEY>>	getReverseNodeIterator()
BTreeLocation<K,STOREKEY>	getStart()
NodeLocation<K,STOREKEY>	getStartNode()
int	hashCode() Return the hash code of the rootKey used to create this tree.
boolean	isEmpty() Return true if the fetched root node has no data in it.
java.util.Set<K>	keySet()
V	put(K key, V value) Put the value into the BTree stored in the NodeStore.
void	putAll(java.util.Map<? extends K,? extends V> m) Calls Map.entrySet() and put(K, V)s each elment.
V	remove(java.lang.Object keyObject) Removes the object from the NodeStore and restructures the BTree.
BTreeSelection<K,STOREKEY>	select(K lower, K upper) Select an inclusive range from lower to upper.
int	size() Iterate through the entire datastrucuture and counts each element.
java.util.Collection<V>	values() Iterate through then entire datastructure and retrieves each element.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll

Constructor Detail

BTree

public BTree(K rootKey,
             NodeStore<K,STOREKEY,V> nodeStore)

Parameters:

rootKey -

nodeStore -

BTree

public BTree(K rootKey,
             NodeStore<K,STOREKEY,V> nodeStore,
             int minData)

Attempt to retrieve the root node stored at the rootKey or, if none is found, construct a new empty root node with minData*2 as the size of the maxData value to the Node's constructors.

The rootKey will never be altered where as internal nodes are not guaranteed to have the same key.

Parameters:

rootKey - The key at which the BTree's root is stored.

nodeStore - The storage engine.

minData - The minimum amount of data that this BTree will store in a Node. The maximum data will be minData*2+1 and the number of child Nodes will be one more than that.

Method Detail

containsKey

public boolean containsKey(java.lang.Object key)

Check the NodeStore for the given key.

Specified by:

containsKey in interface java.util.Map<K,V>

Returns:

true of the key is found in the NodeStore.

clear

public void clear()

Clears the datastructure by doing a depth-first node traversal to delete all the user data and the node data from the NodeStore. This uses eachDepthFirst(com.github.basking2.sdsai.dsds.node.NodeFunction<K, STOREKEY>) to visit each node. Notice that this will not delete the root Node key as other pieces of code may be accessing this object.

Specified by:

clear in interface java.util.Map<K,V>

destroy

public void destroy()

Whereas clearing will destroy all but the root node, this method calls clear() and deletes the root node key.

eachDepthFirst

public void eachDepthFirst(NodeFunction<K,STOREKEY> callable)

Recrusively depth-first execute NodeFunction.call(Node) on each. This is used by clear() to destroy the datastructure in an orderly way. This is the same order provided by getNodeIterator() and NodeLocation.

containsValue

public boolean containsValue(java.lang.Object value)

Specified by:

containsValue in interface java.util.Map<K,V>

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Specified by:

entrySet in interface java.util.Map<K,V>

equals

public boolean equals(java.lang.Object o)

Specified by:

equals in interface java.util.Map<K,V>

Overrides:

equals in class java.lang.Object

keySet

public java.util.Set<K> keySet()

Specified by:

keySet in interface java.util.Map<K,V>

get

public V get(java.lang.Object key)

Retrieve the object from the NodeStore.

Specified by:

get in interface java.util.Map<K,V>

Returns:

The user data returned by NodeStore.loadData(Object).

hashCode

public int hashCode()

Return the hash code of the rootKey used to create this tree.

Specified by:

hashCode in interface java.util.Map<K,V>

Overrides:

hashCode in class java.lang.Object

Returns:

the hash code of the rootKey used to create this tree.

isEmpty

public boolean isEmpty()

Return true if the fetched root node has no data in it.

Specified by:

isEmpty in interface java.util.Map<K,V>

Returns:

true if the fetched root node has no data in it.

put

public V put(K key,
             V value)

Put the value into the BTree stored in the NodeStore. This first checks for the object in NodeStore. If it already exists then no BTree structural change is made and the object is replaced. The old value is returned.

Specified by:

put in interface java.util.Map<K,V>

Parameters:

key - the user key which will be converted to a STOREKEY by NodeStore.convert(Object).

value - The value stored.

putAll

public void putAll(java.util.Map<? extends K,? extends V> m)

Calls Map.entrySet() and put(K, V)s each elment.

Specified by:

putAll in interface java.util.Map<K,V>

remove

public V remove(java.lang.Object keyObject)

Removes the object from the NodeStore and restructures the BTree.

Specified by:

remove in interface java.util.Map<K,V>

Returns:

the object stored at keyObject in the NodeStore.

Throws:

java.lang.ClassCastException - if keyObject is not a key.

size

public int size()

Iterate through the entire datastrucuture and counts each element. Avoid using this.

Specified by:

size in interface java.util.Map<K,V>

values

public java.util.Collection<V> values()

Iterate through then entire datastructure and retrieves each element.

Specified by:

values in interface java.util.Map<K,V>

getStart

public BTreeLocation<K,STOREKEY> getStart()

getEnd

public BTreeLocation<K,STOREKEY> getEnd()

getIterator

public java.util.Iterator<K> getIterator()

Return a BTreeLocation wrapped in an iterator. This will call BTreeLocation.hasNext() and BTreeLocation.next() to iterate through this BTree.

getReverseIterator

public java.util.Iterator<K> getReverseIterator()

Return a BTreeLocation wrapped in an iterator. This will call BTreeLocation.prev() and BTreeLocation.hasPrev() to iterator through the BTree in reverse.

getStartNode

public NodeLocation<K,STOREKEY> getStartNode()

getEndNode

public NodeLocation<K,STOREKEY> getEndNode()

getNodeIterator

public java.util.Iterator<Node<K,STOREKEY>> getNodeIterator()

getReverseNodeIterator

public java.util.Iterator<Node<K,STOREKEY>> getReverseNodeIterator()

getLocation

public BTreeLocation<K,STOREKEY> getLocation(K key)

select

public BTreeSelection<K,STOREKEY> select(K lower,
                                         K upper)

Select an inclusive range from lower to upper.

Parameters:

lower - The lower boundary of the selection, inclusive.

upper - The upper boundary of the selection, exclusive.