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:

BTreeMap<K,V>, java.util.Map<K,V>
```
public class BTree<K,STOREKEY,V>
extends java.lang.Object
implements BTreeMap<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 extends java.lang.Object,V extends java.lang.Object>

Constructor Summary

Constructors
Constructor	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

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	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.
`boolean`	`putKey(K key)`	This function encodes and writes the key into the data structure.
`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,STOREKEY>
    
    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,STOREKEY>
  - 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,STOREKEY>
  - entrySet
```
public java.util.Set<java.util.Map.Entry<K,V>> entrySet()
```
    Specified by:
    
    entrySet in interface java.util.Map<K,STOREKEY>
  - equals
```
public boolean equals(java.lang.Object o)
```
    Specified by:
    
    equals in interface java.util.Map<K,STOREKEY>
    
    Overrides:
    
    equals in class java.lang.Object
  - keySet
```
public java.util.Set<K> keySet()
```
    Specified by:
    
    keySet in interface java.util.Map<K,STOREKEY>
  - get
```
public V get(java.lang.Object key)
```
    Retrieve the object from the NodeStore.
    
    Specified by:
    
    get in interface java.util.Map<K,STOREKEY>
    
    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,STOREKEY>
    
    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,STOREKEY>
    
    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,STOREKEY>
    
    Parameters:
    
    key - the user key which will be converted to a STOREKEY by NodeStore.convert(Object).
    
    value - The value stored.
  - putKey
```
public boolean putKey(K key)
```
    This function encodes and writes the key into the data structure. This is useful for situations where the user data is already in a data store and we are just building additional indexes to it.
    
    Specified by:
    
    putKey in interface BTreeMap<K,STOREKEY>
    
    Parameters:
    
    key - The key to add to the structure.
    
    Returns:
    
    True if the key was inserted. False if the key already existed.
  - 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,STOREKEY>
  - 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,STOREKEY>
    
    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,STOREKEY>
  - 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,STOREKEY>
  - 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.

Class BTree<K,​STOREKEY,​V>

Nested Class Summary

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

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Map

Constructor Detail

BTree

BTree

Method Detail

containsKey

clear

destroy

eachDepthFirst

containsValue

entrySet

equals

keySet

get

hashCode

isEmpty

put

putKey

putAll

remove

size

values

getStart

getEnd

getIterator

getReverseIterator

getStartNode

getEndNode

getNodeIterator

getReverseNodeIterator

getLocation

select

Class BTree<K,STOREKEY,V>