Packages

  • package root
    Definition Classes
    root
  • package xyz
    Definition Classes
    root
  • package hyperreal
    Definition Classes
    xyz
  • package btree

    Provides an abstract class for building and using B+ Trees.

    Provides an abstract class for building and using B+ Trees.

    Overview

    The class to extend is BPlusTree. It is designed to be both generic (type parameters for keys and values, and an abstract type for node references) and general (doesn't care how the tree is stored). An extending class needs to implement a number of simple methods and node type that provide storage independence.

    There are two examples that extend AbstractBPlusTree: MemoryBPlusTree and FileBPlusTree. MemoryBPlusTree implements a B+ Tree in-memory and is essentially a map implementation. FileBPlusTree implements a B+ Tree on-disk and is sort-of a very simple database.

    Definition Classes
    hyperreal
  • BPlusTree
  • FileBPlusTree
  • FileBPlusTreeFormat
  • MemoryBPlusTree
  • MutableSortedMap

class FileBPlusTree[K, V] extends BPlusTree[K, V] with FileBPlusTreeFormat

An on-disk B+ Tree implementation.

K

the type of the keys contained in this map.

V

the type of the values associated with the keys.

Linear Supertypes
FileBPlusTreeFormat, BPlusTree[K, V], AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. FileBPlusTree
  2. FileBPlusTreeFormat
  3. BPlusTree
  4. AnyRef
  5. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new FileBPlusTree(filename: String, order: Int, synchronous: Boolean = false)(implicit arg0: (K) ⇒ Ordered[K])

    creates an object to provide access to the root B+ Tree contained within the file at filename with a branching factor of order.

    creates an object to provide access to the root B+ Tree contained within the file at filename with a branching factor of order. The on-disk tree's order must be equal to order or an exception will be thrown. This is the constructor that would normally be used to access a B+ tree file.

    filename

    path to the file to contain the tree. The file created is completely self contained: if the file alread exists (and newfile is false) then the object opens the file and provides continued access to the tree

    order

    the branching factor (maximum number of branches in an internal node) of the tree

    synchronous

    true causes any changes to the file to be written to disk immediately, false is the default

  2. new FileBPlusTree(file: RandomAccessFile, tree: Long, order: Int)(implicit arg0: (K) ⇒ Ordered[K])

    creates an object to provide access to a B+ Tree contained within file with it's tree descriptor record at offset tree and with a branching factor of order.

    creates an object to provide access to a B+ Tree contained within file with it's tree descriptor record at offset tree and with a branching factor of order. The on-disk tree's order must be equal to order or an exception will be thrown. This constructor is used internally to access a B+ tree that is a value in another B+ tree.

    file

    the java.io.RandomAccessFile to be used to access the B+ tree

    tree

    the offset within file of the tree's descriptor record

    order

    the branching factor (maximum number of branches in an internal node) of the tree

Type Members

  1. type N = Long

    Abstract node type.

    Abstract node type. For in-memory implementations this would probably be the actual node class and for on-disk it would likely be the file pointer where the node is stored.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
    Note

    Comparing two nodes for equality is required to be true when they point to the same node.

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. val BLOCK_SIZE: Int
  5. val DATA_ARRAY_SIZE: Int
  6. val DATUM_SIZE: Int
  7. val FILE_BLOCKS: Int
    Definition Classes
    FileBPlusTreeFormat
  8. val FILE_FREE_PTR: Int
    Definition Classes
    FileBPlusTreeFormat
  9. val FILE_HEADER: Int
    Definition Classes
    FileBPlusTreeFormat
  10. val FILE_HEADER_SIZE: Int
    Definition Classes
    FileBPlusTreeFormat
  11. val FILE_ORDER: Int
    Definition Classes
    FileBPlusTreeFormat
  12. val FILE_ROOT_RECORD: Int
    Definition Classes
    FileBPlusTreeFormat
  13. val INTERNAL_BRANCHES: Int
  14. val INTERNAL_NODE: Int
  15. val LEAF_NODE: Int
  16. val LEAF_VALUES: Int
  17. val NODE_KEYS: Int
  18. val NODE_LENGTH: Int
  19. val NODE_NEXT_PTR: Int
  20. val NODE_PARENT_PTR: Int
  21. val NODE_PREV_PTR: Int
  22. val NODE_TYPE: Int
  23. val NUL: Int
  24. val POINTER_SIZE: Int
    Definition Classes
    FileBPlusTreeFormat
  25. val TREE_FIRST_PTR: Int
    Definition Classes
    FileBPlusTreeFormat
  26. val TREE_LAST_PTR: Int
    Definition Classes
    FileBPlusTreeFormat
  27. val TREE_RECORD_SIZE: Int
    Definition Classes
    FileBPlusTreeFormat
  28. val TREE_ROOT_PTR: Int
    Definition Classes
    FileBPlusTreeFormat
  29. val TYPE_ARRAY: Int
  30. val TYPE_BOOLEAN: Int
  31. val TYPE_BOOLEAN_FALSE: Int
  32. val TYPE_BOOLEAN_TRUE: Int
  33. val TYPE_DOUBLE: Int
  34. val TYPE_INT: Int
  35. val TYPE_LONG: Int
  36. val TYPE_MAP: Int
  37. val TYPE_NULL: Int
  38. val TYPE_STRING: Int
  39. def addBranch(node: Long, branch: Long): Unit

    Adds a new branch to (internal) node.

    Adds a new branch to (internal) node. branch is placed at an index equal to the length of node, given that the length of a node is the number of keys.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  40. def addKey(node: Long, key: K): Unit

    Adds a new key to node.

    Adds a new key to node. The length of node will increase by one as a result. This method should be called before either addBranch or addValue since those methods use the current node length to determine placemenet.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  41. def alloc(size: Int): Long
    Attributes
    protected
  42. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  43. def binarySearch(node: N, target: K): Int

    Performs a binary search for key target within node (tail recursively).

    Performs a binary search for key target within node (tail recursively).

    returns

    the index of target within node if it exists, or (-insertionPoint - 1) where insertionPoint is the index of the correct insertion point for key target.

    Attributes
    protected
    Definition Classes
    BPlusTree
  44. def boundedIterator(bounds: (Symbol, K)*): Iterator[(K, V)]

    Returns a bounded iterator over a range of key/value pairs in the tree in ascending sorted key order.

    Returns a bounded iterator over a range of key/value pairs in the tree in ascending sorted key order. The range of key/value pairs in the iterator is specified by bounds. bounds must contain one or two pairs where the first element in the pair is a symbol corresponding to the type of bound (i.e. '<, '<=, '>, '>=) and the second element is a key value.

    An example of a bounded iterator over all elements in a tree (with String keys) that will include all keys that sort greater than or equal to "a" and up to but not including "e" is boundedIterator( ('>=, "a"), ('<, "e") ).

    Definition Classes
    BPlusTree
  45. def boundedKeysIterator(bounds: (Symbol, K)*): Iterator[K]

    Returns a bounded iterator over a range of keys in the tree in ascending sorted key order.

    Returns a bounded iterator over a range of keys in the tree in ascending sorted key order. The bounds parameter is the same as for boundedIterator.

    Definition Classes
    BPlusTree
  46. def boundedPositionIterator(bounds: (Symbol, K)*): Iterator[(N, Int)]

    Returns a bounded iterator over a range of key positions (node/index pairs) in the tree in ascending sorted key order.

    Returns a bounded iterator over a range of key positions (node/index pairs) in the tree in ascending sorted key order. The bounds parameter is the same as for boundedIterator.

    Attributes
    protected
    Definition Classes
    BPlusTree
  47. def boundedValuesIterator(bounds: (Symbol, K)*): Iterator[V]

    Returns a bounded iterator over a range of values in the tree in ascending sorted key order.

    Returns a bounded iterator over a range of values in the tree in ascending sorted key order. The bounds parameter is the same as for boundedIterator.

    Definition Classes
    BPlusTree
  48. def build(s: String): BPlusTree[K, V]

    Returns a B+ tree build from a string representation of the tree.

    Returns a B+ tree build from a string representation of the tree. The syntax of the input string is simple: internal nodes are coded as lists of nodes alternating with keys (alpha strings with no quotation marks) using parentheses with elements separated by space, leaf nodes are coded as lists of alpha strings (no quotation marks) using brackets with elements separated by space.

    Definition Classes
    BPlusTree
    Example: 

    1. (
  [g] j [j t] u [u v]
)

      produces a tree that pretty prints as

      [n0: (null, null, null) n1 | j | n2 | u | n3]
[n1: (null, n0, n2) g] [n2: (n1, n0, n3) j t] [n3: (n2, n0, null) u v]
  49. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  50. def close: Unit
  51. def copyInternal(src: Long, begin: Int, end: Int, dst: Long, index: Int): Unit
    Attributes
    protected
  52. def copyKeys(src: Long, begin: Int, end: Int, dst: Long, index: Int): Array[Byte]
    Attributes
    protected
  53. def copyLeaf(src: Long, begin: Int, end: Int, dst: Long, index: Int): Unit
    Attributes
    protected
  54. def decode(in: DataInput): Any
    Attributes
    protected
  55. def delete(key: K): Boolean

    Performs the B+ tree deletion algorithm to remove key and it's associated value from the tree, rebalancing the tree if necessary.

    Performs the B+ tree deletion algorithm to remove key and it's associated value from the tree, rebalancing the tree if necessary.

    returns

    true if key was found (and therefore removed), false otherwise

    Definition Classes
    BPlusTree
  56. def diagram(name: String): Unit

    Creates a PNG image file called name (with .png added) which visually represents the structure and contents of the tree, only showing the keys.

    Creates a PNG image file called name (with .png added) which visually represents the structure and contents of the tree, only showing the keys. This method uses GraphViz (specifically the dot command) to produce the diagram, and ImageMagik (specifically the convert command) to convert it from SVG to PNG. dot can product PNG files directly but I got better results producing SVG and converting to PNG.

    Definition Classes
    BPlusTree
  57. def dispose(addr: Long): Unit
    Attributes
    protected
  58. def encode(out: DataOutput, datum: Any): Unit
    Attributes
    protected
  59. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  60. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  61. val file: RandomAccessFile
    Attributes
    protected
  62. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  63. var first: Long
    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  64. def free(start: Long, size: Int): Unit
    Attributes
    protected
  65. def freeKey(node: N, index: Int): Unit

    Free the storage previously allocated for the key at index in node.

    Free the storage previously allocated for the key at index in node. For in-memory implementations, this method probably won't do anything.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  66. def freeNode(node: Long): Unit

    Free the storage previously allocated for node.

    Free the storage previously allocated for node. For in-memory implementations, this method probably won't do anything.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  67. def freeValue(node: N, index: Int): Unit

    Free the storage previously allocated for the value at index in node.

    Free the storage previously allocated for the value at index in node. For in-memory implementations, this method probably won't do anything.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  68. def getBranch(node: Long, index: Int): N

    Returns a branch pointer from an internal node at a given index.

    Returns a branch pointer from an internal node at a given index. There is always one more branch pointer than there are keys in an internal node so the highest index is equal to nodeLength( node ).

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  69. def getBranches(node: Long): Seq[Long]

    Returns the branches of node as a non-strict immutable sequence.

    Returns the branches of node as a non-strict immutable sequence.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  70. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  71. def getKey(node: Long, index: Int): K

    Returns a key from a leaf node at a given index.

    Returns a key from a leaf node at a given index.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  72. def getKeyValue(leaf: N, index: Int): (K, V)

    Returns the key/value pair at index within leaf.

    Returns the key/value pair at index within leaf.

    Attributes
    protected
    Definition Classes
    BPlusTree
  73. def getKeys(node: Long): Seq[K]

    Returns the keys of node as a non-strict immutable sequence.

    Returns the keys of node as a non-strict immutable sequence.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  74. def getNext(node: Long): Long

    Returns the next pointer of (leaf) node.

    Returns the next pointer of (leaf) node.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  75. def getParent(node: Long): Long

    Returns the parent pointer of node.

    Returns the parent pointer of node.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  76. def getPrev(node: Long): Long

    Returns the previous leaf node link pointer of (leaf) node.

    Returns the previous leaf node link pointer of (leaf) node.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  77. def getValue(node: Long, index: Int): V

    Returns a value from a leaf node at a given index.

    Returns a value from a leaf node at a given index.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  78. def getValues(node: Long): AbstractSeq[V] with IndexedSeq[V]

    Returns the values of node as a non-strict immutable sequence.

    Returns the values of node as a non-strict immutable sequence.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  79. def greatestLT(key: K): (N, Int)

    Returns the leaf position of the key that is greatest less than key.

    Returns the leaf position of the key that is greatest less than key.

    Attributes
    protected
    Definition Classes
    BPlusTree
  80. def greatestLTE(key: K): (N, Int)

    Returns the leaf position of the key that is greatest less than or equal to key.

    Returns the leaf position of the key that is greatest less than or equal to key.

    Attributes
    protected
    Definition Classes
    BPlusTree
  81. def greatestLessThan(key: K): Option[(K, V)]

    Returns the key/value pair whose key is greatest less than key.

    Returns the key/value pair whose key is greatest less than key.

    Definition Classes
    BPlusTree
  82. def greatestLessThanOrEqual(key: K): Option[(K, V)]

    Returns the key/value pair whose key is greatest less than or equal to key.

    Returns the key/value pair whose key is greatest less than or equal to key.

    Definition Classes
    BPlusTree
  83. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  84. def insert[V1 >: V](key: K, value: V1 = null.asInstanceOf[V1]): Boolean

    Inserts key with associated value into the tree.

    Inserts key with associated value into the tree. If key exists, then it's new associated value will be value.

    returns

    true if key exists

    Definition Classes
    BPlusTree
  85. def insertAt[V1 >: V](key: K, value: V1, leaf: N, index: Int): Unit

    Performs the B+ tree insertion algorithm to insert key and associated value into the tree, specifically in leaf at index, rebalancing the tree if necessary.

    Performs the B+ tree insertion algorithm to insert key and associated value into the tree, specifically in leaf at index, rebalancing the tree if necessary. If leaf and index is not the correct insertion point for key then this method will probably result in an invalid B+ tree.

    Attributes
    protected
    Definition Classes
    BPlusTree
  86. def insertIfNotFound[V1 >: V](key: K, value: V1 = null.asInstanceOf[V1]): Boolean

    Inserts key with associated value into the tree only if key does not exist.

    Inserts key with associated value into the tree only if key does not exist.

    returns

    true if key exists

    Definition Classes
    BPlusTree
  87. def insertInternal(node: Long, keyIndex: Int, key: K, branchIndex: Int, branch: Long): Unit

    Inserts key and branch into (internal) node at keyIndex and branchIndex, respectively.

    Inserts key and branch into (internal) node at keyIndex and branchIndex, respectively.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  88. def insertKeys(keys: K*): Unit

    Inserts keys into the tree each with an associated value of null.

    Inserts keys into the tree each with an associated value of null. If a given key exists, then it's new associated value will be null.

    Definition Classes
    BPlusTree
  89. def insertKeysAndCheck(keys: K*): String

    Inserts keys into the tree each with an associated value of null, and checks that the tree is well constructed after each key is inserted.

    Inserts keys into the tree each with an associated value of null, and checks that the tree is well constructed after each key is inserted. If a given key exists, then it's new associated value will be null. This method is used for testing.

    Definition Classes
    BPlusTree
  90. def insertLeaf[V1 >: V](node: Long, index: Int, key: K, value: V1): Unit

    Inserts key and value into (leaf) node at index.

    Inserts key and value into (leaf) node at index.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  91. def isEmpty: Boolean

    Returns true is the tree is empty.

    Returns true is the tree is empty.

    Definition Classes
    BPlusTree
  92. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  93. def isLeaf(node: Long): Boolean

    Returns true if node is a leaf node

    Returns true if node is a leaf node

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  94. def iterator: Iterator[(K, V)]

    Returns an iterator over all key/value pairs in the tree in ascending sorted key order.

    Returns an iterator over all key/value pairs in the tree in ascending sorted key order.

    Definition Classes
    BPlusTree
  95. def keys: Iterable[K]

    Returns a non-strict Iterable containing the keys in the tree.

    Returns a non-strict Iterable containing the keys in the tree.

    Definition Classes
    BPlusTree
  96. def keysIterator: Iterator[K]

    Returns an iterator over all keys in the tree in ascending sorted order.

    Returns an iterator over all keys in the tree in ascending sorted order.

    Definition Classes
    BPlusTree
  97. var last: Long
    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  98. var lastlen: Int
    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  99. def leastGT(key: K): (N, Int)

    Returns the leaf position of the key that is least greater than key.

    Returns the leaf position of the key that is least greater than key.

    Attributes
    protected
    Definition Classes
    BPlusTree
  100. def leastGTE(key: K): (N, Int)

    Returns the leaf position of the key that is least greater than or equal to key.

    Returns the leaf position of the key that is least greater than or equal to key.

    Attributes
    protected
    Definition Classes
    BPlusTree
  101. def leastGreaterThan(key: K): Option[(K, V)]

    Returns the key/value pair whose key is least greater than key.

    Returns the key/value pair whose key is least greater than key.

    Definition Classes
    BPlusTree
  102. def leastGreaterThanOrEqual(key: K): Option[(K, V)]

    Returns the key/value pair whose key is least greater than or equal to key.

    Returns the key/value pair whose key is least greater than or equal to key.

    Definition Classes
    BPlusTree
  103. def leftmost(node: N): K

    Returns the left most or least key within or under node.

    Returns the left most or least key within or under node.

    Attributes
    protected
    Definition Classes
    BPlusTree
  104. def load[V1 >: V](kvs: (K, V1)*): Unit

    Performs the B+ tree bulk loading algorithm to insert key/value pairs kvs into the tree efficiently.

    Performs the B+ tree bulk loading algorithm to insert key/value pairs kvs into the tree efficiently. This method is more efficient than using insert because insert performs a search to determine the correct insertion point for the key whereas load does not. load can only work if the tree is empty, or if the minimum key to be inserted is greater than the maximum key in the tree.

    Definition Classes
    BPlusTree
  105. def lookup(key: K): (Boolean, N, Int)

    Performs the B+ tree lookup algorithm (tail recursively) beginning at the root, in search of the location (if found) or correct insertion point (if not found) of key.

    Performs the B+ tree lookup algorithm (tail recursively) beginning at the root, in search of the location (if found) or correct insertion point (if not found) of key.

    returns

    a triple where the first element is true if key exists and false otherwise, the second element is the node containing key if found or the correct insertion point for key if not found, the third is the index within that node.

    Attributes
    protected
    Definition Classes
    BPlusTree
  106. def lookupGTE(key: K): (Boolean, N, Int)

    Searches for key returning a point in a leaf node that is the least greater than (if not found) or equal to (if found) key.

    Searches for key returning a point in a leaf node that is the least greater than (if not found) or equal to (if found) key. The leaf node and index returned in case key does not exist is not necessarily the correct insertion point. This method is used by boundedIterator.

    returns

    a triple where the first element is true if key exists and false otherwise, and the second element is the leaf node containing the least greater than or equal key, and the third is the index of that key.

    Attributes
    protected
    Definition Classes
    BPlusTree
  107. def lookupLTE(key: K): (Boolean, N, Int)

    Searches for key returning a point in a leaf node that is the greatest less than (if not found) or equal to (if found) key.

    Searches for key returning a point in a leaf node that is the greatest less than (if not found) or equal to (if found) key. The leaf node and index returned in case key does not exist is not necessarily the correct insertion point. This method is used by reverseBoundedIterator.

    returns

    a triple where the first element is true if key exists and false otherwise, and the second element is the leaf node containing the greatest less than or equal key, and the third is the index of that key.

    Attributes
    protected
    Definition Classes
    BPlusTree
  108. def max: Option[(K, V)]

    Returns the maximum key and it's associated value.

    Returns the maximum key and it's associated value.

    returns

    Some( (key, value) ) where key is the maximum key and value is it's associated value if the tree is non-empty, or None if the tree is empty.

    Definition Classes
    BPlusTree
  109. def maxKey: Option[K]

    Returns the maximum key.

    Returns the maximum key.

    Definition Classes
    BPlusTree
  110. def min: Option[(K, V)]

    Returns the minimum key and it's associated value.

    Returns the minimum key and it's associated value.

    returns

    Some( (key, value) ) where key is the minimum key and value is it's associated value if the tree is non-empty, or None if the tree is empty.

    Definition Classes
    BPlusTree
  111. def minKey: Option[K]

    Returns the minimum key.

    Returns the minimum key.

    Definition Classes
    BPlusTree
  112. val minlen: Int

    The minimum length (number of keys) that a non-root node (internal or leaf) may have is ceil(order/2) - 1.

    The minimum length (number of keys) that a non-root node (internal or leaf) may have is ceil(order/2) - 1. The minimum length for a root leaf node is 0. The minimum length for a root internal node is 1.

    Attributes
    protected
    Definition Classes
    BPlusTree
  113. def moveInternal(src: Long, begin: Int, end: Int, dst: Long, index: Int): Unit

    Moves key/branch pairs from node src beginning at index begin up to but not including index end to node dst at index.

    Moves key/branch pairs from node src beginning at index begin up to but not including index end to node dst at index.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  114. def moveLeaf(src: Long, begin: Int, end: Int, dst: Long, index: Int): Unit

    Moves key/value pairs from node src to node dst beginning at index begin and ending up to but not including index end.

    Moves key/value pairs from node src to node dst beginning at index begin and ending up to but not including index end.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  115. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  116. def newInternal(parent: Long): Long

    Creates a new internal node with parent as its parent pointer.

    Creates a new internal node with parent as its parent pointer.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  117. def newLeaf(parent: Long): Long

    Creates a new leaf node with parent as its parent pointer.

    Creates a new leaf node with parent as its parent pointer.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  118. def newRoot(branch: Long): Long

    Creates a new root (internal) node with branch as its leftmost branch pointer and null parent pointer.

    Creates a new root (internal) node with branch as its leftmost branch pointer and null parent pointer. Implementations are require to update the in-storage copy of the root pointer if needed (only really applies to on-disk implementations).

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  119. def nextPosition(leaf: N, index: Int): (N, Int)

    Returns the node/index pair pointing to the location of the leaf node key following the one at index in leaf.

    Returns the node/index pair pointing to the location of the leaf node key following the one at index in leaf.

    Attributes
    protected
    Definition Classes
    BPlusTree
  120. def nodeLength(node: Long, len: Int): Unit
    Attributes
    protected
  121. def nodeLength(node: Long): Int

    Returns the length (number of keys) of node.

    Returns the length (number of keys) of node. For internal nodes, the number of branch pointers will one more than the length.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  122. final def notify(): Unit
    Definition Classes
    AnyRef
  123. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  124. def nul: Long

    Returns the null node pointer.

    Returns the null node pointer. For in-memory implementations this will usually be a Scala null value. For on-disk it would make sense for this to be 0L.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  125. def optionalKey(pos: (N, Int)): Option[K]
    Attributes
    protected
    Definition Classes
    BPlusTree
  126. def optionalKeyValue(pos: (N, Int)): Option[(K, V)]
    Attributes
    protected
    Definition Classes
    BPlusTree
  127. val order: Int
    Definition Classes
    FileBPlusTree → BPlusTree
  128. def positionIterator: Iterator[(N, Int)]

    Returns an iterator over all key positions (node/index pairs) in the tree in ascending sorted key order.

    Returns an iterator over all key positions (node/index pairs) in the tree in ascending sorted key order.

    Attributes
    protected
    Definition Classes
    BPlusTree
  129. def prettyPrint: Unit

    Prints (to stdout) a readable representation of the structure and contents of the tree.

    Prints (to stdout) a readable representation of the structure and contents of the tree.

    Definition Classes
    BPlusTree
  130. def prettyPrintKeysOnly: Unit

    Prints (to stdout) a readable representation of the structure and contents of the tree, omitting the values and only printing the keys.

    Prints (to stdout) a readable representation of the structure and contents of the tree, omitting the values and only printing the keys.

    Definition Classes
    BPlusTree
  131. def prettySearch(key: K): String

    Returns a string representing a search result for key that will be consistant with prettyPrint.

    Returns a string representing a search result for key that will be consistant with prettyPrint. This method is used mainly for unit testing.

    Definition Classes
    BPlusTree
  132. def prettyString: String

    Returns a string containing a readable representation of the structure and contents of the tree, omitting the values and only printing the keys.

    Returns a string containing a readable representation of the structure and contents of the tree, omitting the values and only printing the keys. This method is used mainly for unit testing.

    Definition Classes
    BPlusTree
  133. def prettyStringWithValues: String

    Returns a string containing a readable representation of the structure and contents of the tree.

    Returns a string containing a readable representation of the structure and contents of the tree. This method is used mainly for unit testing.

    Definition Classes
    BPlusTree
  134. def prevPosition(leaf: N, index: Int): (N, Int)

    Returns the node/index pair pointing to the location of the leaf node key preceding the one at index in leaf.

    Returns the node/index pair pointing to the location of the leaf node key preceding the one at index in leaf.

    Attributes
    protected
    Definition Classes
    BPlusTree
  135. def readDatumArray(array: Array[Byte], index: Int): Any
    Attributes
    protected
  136. def readDatumFile(addr: Long): Any
    Attributes
    protected
  137. def removeInternal(node: Long, keyIndex: Int, branchIndex: Int): Int

    Removes the key and branch pair from internal node at keyIndex and branchIndex, respectively.

    Removes the key and branch pair from internal node at keyIndex and branchIndex, respectively. This method is perhaps poorly named: it does not remove an internal node from the tree.

    returns

    length of node after removal

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  138. def removeLeaf(node: Long, index: Int): Int

    Removes the key/value pair from leaf node at index.

    Removes the key/value pair from leaf node at index. This method is perhaps poorly named: it does not remove a leaf node from the tree.

    returns

    length of node after removal

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  139. def reverseBoundedIterator(bounds: (Symbol, K)*): Iterator[(K, V)]

    Returns a bounded iterator over a range of key/value pairs in the tree in descending sorted key order.

    Returns a bounded iterator over a range of key/value pairs in the tree in descending sorted key order. The range of key/value pairs in the iterator is specified by bounds. bounds must contain one or two pairs where the first element in the pair is a symbol corresponding to the type of bound (i.e. '<, '<=, '>, '>=) and the second element is a key value.

    An example of a reverse bounded iterator over all elements in a tree (with String keys) that will include all keys that sort greater than or equal to "a" and up to but not including "e", iterated over in reverse order, is reverseBoundedIterator( ('>=, "a"), ('<, "e") ).

    Definition Classes
    BPlusTree
  140. def reverseBoundedKeysIterator(bounds: (Symbol, K)*): Iterator[K]

    Returns a bounded iterator over a range of keys in the tree in descending sorted key order.

    Returns a bounded iterator over a range of keys in the tree in descending sorted key order. The bounds parameter is the same as for boundedIterator.

    Definition Classes
    BPlusTree
  141. def reverseBoundedPositionIterator(bounds: (Symbol, K)*): Iterator[(N, Int)]

    Returns a bounded iterator over a range of key positions (node/index pairs) in the tree in descending sorted key order.

    Returns a bounded iterator over a range of key positions (node/index pairs) in the tree in descending sorted key order. The bounds parameter is the same as for boundedIterator.

    Attributes
    protected
    Definition Classes
    BPlusTree
  142. def reverseBoundedValuesIterator(bounds: (Symbol, K)*): Iterator[V]

    Returns a bounded iterator over a range of values in the tree in descending sorted key order.

    Returns a bounded iterator over a range of values in the tree in descending sorted key order. The bounds parameter is the same as for boundedIterator.

    Definition Classes
    BPlusTree
  143. def reverseIterator: Iterator[(K, V)]

    Returns an iterator over all key/value pairs in the tree in descending sorted key order.

    Returns an iterator over all key/value pairs in the tree in descending sorted key order.

    Definition Classes
    BPlusTree
  144. def reverseKeysIterator: Iterator[K]

    Returns a reverse iterator over all keys in the tree in descending sorted order.

    Returns a reverse iterator over all keys in the tree in descending sorted order.

    Definition Classes
    BPlusTree
  145. def reversePositionIterator: Iterator[(N, Int)]

    Returns a reverse iterator over all key positions (node/index pairs) in the tree in descending sorted key order.

    Returns a reverse iterator over all key positions (node/index pairs) in the tree in descending sorted key order.

    Attributes
    protected
    Definition Classes
    BPlusTree
  146. def rightmost(node: N): K

    Returns the right most or greatest key within or under node.

    Returns the right most or greatest key within or under node.

    Attributes
    protected
    Definition Classes
    BPlusTree
  147. var root: Long
    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  148. def search(key: K): Option[V]

    Searches for key returning it's associated value if key exists.

    Searches for key returning it's associated value if key exists.

    returns

    Some( value ) where value is the value associated to key if it exists, or None otherwise

    Definition Classes
    BPlusTree
  149. def serialize(before: String, prefix: String, internalnode: (N, (N) ⇒ String, (String) ⇒ Unit) ⇒ String, leafnode: (N, (N) ⇒ String) ⇒ String, after: String): String

    Returns a serialization (string representation of the tree) using string and function arguments to specify the exact form of the serialization.

    Returns a serialization (string representation of the tree) using string and function arguments to specify the exact form of the serialization. This method is used for pretty printing and to generate a DOT (graph description language) description of the tree so that it can be visualized.

    before

    string to be prepended to the serialization

    prefix

    string to be place before each line of the serialization that includes internal and leaf nodes

    internalnode

    function to generate internal node serializations using three parameters: the current node, a function to return a string id of a node, a function that allows a line of text to be appended after all nodes have been serialized

    leafnode

    function to generate leaf node serializations using two parameters: the current node, a function to return a string id of a node

    after

    string to be appended to the serialization

    Attributes
    protected
    Definition Classes
    BPlusTree
  150. def setBranch(node: Long, index: Int, branch: Long): Unit
    Attributes
    protected
  151. def setFirst(leaf: Long): Unit

    Sets the in-storage copy of the first leaf node pointer.

    Sets the in-storage copy of the first leaf node pointer. This method is not responsable for setting the first variable.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  152. def setKey(node: Long, index: Int, key: K): Unit

    Sets the key at index of node to key.

    Sets the key at index of node to key.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  153. def setLast(leaf: Long): Unit

    Sets the in-storage copy of the last leaf node pointer.

    Sets the in-storage copy of the last leaf node pointer. This method is not responsable for setting the last variable nor the lastlen variable.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  154. def setNext(node: Long, p: Long): Unit

    Sets the next pointer of (leaf) node to p.

    Sets the next pointer of (leaf) node to p.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  155. def setParent(node: Long, p: Long): Unit

    Sets the parent pointer of node to p.

    Sets the parent pointer of node to p.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  156. def setPrev(node: Long, p: Long): Unit

    Sets previous leaf node link pointer of (leaf) node to p.

    Sets previous leaf node link pointer of (leaf) node to p.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  157. def setRoot(node: Long): Unit

    Sets the in-storage copy of the root node pointer.

    Sets the in-storage copy of the root node pointer. This method is not responsable for setting the root variable.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  158. def setValue[V1 >: V](node: Long, index: Int, v: V1): Unit

    Sets the value at index of node to v.

    Sets the value at index of node to v.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  159. def str(n: Long): String

    Returns a string representation of the keys in node.

    Returns a string representation of the keys in node. This method was used in debugging FileBPlusTree since the node type is Long.

    Attributes
    protected
    Definition Classes
    FileBPlusTree → BPlusTree
  160. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  161. def toString(): String
    Definition Classes
    AnyRef → Any
  162. def traverseBreadthFirst(level: (List[N]) ⇒ Unit): Unit

    Performs a breadth first traversal of the tree (tail recursively), applying level to each level of the tree beginning at the root.

    Performs a breadth first traversal of the tree (tail recursively), applying level to each level of the tree beginning at the root.

    Attributes
    protected
    Definition Classes
    BPlusTree
  163. val tree: Long
    Attributes
    protected
  164. def valuesIterator: Iterator[V]

    Returns an iterator over all values in the tree in the order corresponding to ascending keys.

    Returns an iterator over all values in the tree in the order corresponding to ascending keys.

    Definition Classes
    BPlusTree
  165. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  166. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  167. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  168. def wellConstructed: String

    Analyzes the tree to determine if it is well constructed.

    Analyzes the tree to determine if it is well constructed.

    returns

    "true" (as a string) if the tree is a well constructed B+ tree, a string description of the flaw otherwise.

    Definition Classes
    BPlusTree
  169. def writeDatumArray(array: Array[Byte], index: Int, datum: Any): Unit
    Attributes
    protected
  170. def writeDatumFile(addr: Long, datum: Any): Unit
    Attributes
    protected
  171. def writeEmptyRecord(node: Long): Unit
    Attributes
    protected

Inherited from FileBPlusTreeFormat

Inherited from BPlusTree[K, V]

Inherited from AnyRef

Inherited from Any

Ungrouped