package 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.
- Alphabetic
- By Inheritance
- btree
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Type Members
-
abstract
class
BPlusTree
[K, +V] extends AnyRef
Provides for interaction (searching, insertion, update, deletion) with a B+ tree that can be stored anywhere (in memory, on disk).
Provides for interaction (searching, insertion, update, deletion) with a B+ tree that can be stored anywhere (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
firstandlastshould refer to the root leaf node, and thelastlenvariable 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
truewhen 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]
Value Members
- object FileBPlusTree extends FileBPlusTreeFormat
- object MutableSortedMap