btree

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.

Linear Supertypes

AnyRef, Any

Type Members

abstract class BPlusTree[K, +V] extends AnyRef

Provides for interaction (searching, insertion, update, deletion) with a B+ tree that can be stored any where (in memory, on disk).
Provides for interaction (searching, insertion, update, deletion) with a B+ tree that can be stored any where (in memory, on disk). It is the implementation's responsability to create the empty B+ tree initially. An empty B+ tree consists of a single empty leaf node as the root. Also the first and last should refer to the root leaf node, and the lastlen variable should be 0. For on-disk implementations it should be possible to open an existing B+ tree or optionally create a new one.
A B+ tree is composed of nodes that are linked to one another using pointers. The exact way in which the nodes are layed out and stored is left to the implementation. Also, node pointers are left to the implementation through the abstract node type. There is a very important implementation requirement that comparing two nodes for equality return true when they point to the same node. All nodes have
- a parent pointer
- a next pointer to the right sibling
- a prev pointer to the left sibling
- an array of keys
There are two kinds nodes:
- leaf nodes, containing an array of values each corresponding to it's associated key in the keys array.
- internal nodes, containing an array of branch pointers. This array always has one element more than the number of keys.
K
the type of the keys contained in this map.
V
the type of the values associated with the keys.
class FileBPlusTree[K, V] extends BPlusTree[K, V] with FileBPlusTreeFormat

An on-disk B+ Tree implementation.
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.
trait FileBPlusTreeFormat extends AnyRef
class MemoryBPlusTree[K, V] extends BPlusTree[K, V]

An in-memory B+ Tree implementation.
An in-memory B+ Tree implementation.
K
the type of the keys contained in this map.
V
the type of the values associated with the keys.
class MutableSortedMap[K, V] extends SortedMap[K, V]

package btree

Overview

Type Members

abstract class BPlusTree[K, +V] extends AnyRef

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

trait FileBPlusTreeFormat extends AnyRef

class MemoryBPlusTree[K, V] extends BPlusTree[K, V]

class MutableSortedMap[K, V] extends SortedMap[K, V]

Value Members

object FileBPlusTree extends FileBPlusTreeFormat

object MutableSortedMap

Inherited from AnyRef

Inherited from Any

Ungrouped