Copyright | Jeremy Groven |
---|---|
License | BSD3 |
Safe Haskell | None |
Language | Haskell2010 |
Definitions of primitive types used in different modules of stable-tree
- type Depth = Int
- type ValueCount = Int
- data StableTree k v
- = forall d . StableTree_I (Tree d Incomplete k v)
- | forall d . StableTree_C (Tree d Complete k v)
- data Incomplete
- data Complete
- data Z
- data S a
- data Tree d c k v where
- Bottom :: (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> (Key Terminal k, v) -> Tree Z Complete k v
- IBottom0 :: Maybe (SomeKey k, v) -> Tree Z Incomplete k v
- IBottom1 :: (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> Tree Z Incomplete k v
- Branch :: Depth -> (SomeKey k, ValueCount, Tree d Complete k v) -> (SomeKey k, ValueCount, Tree d Complete k v) -> Map (Key Nonterminal k) (ValueCount, Tree d Complete k v) -> (Key Terminal k, ValueCount, Tree d Complete k v) -> Tree (S d) Complete k v
- IBranch0 :: Depth -> (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v
- IBranch1 :: Depth -> (SomeKey k, ValueCount, Tree d Complete k v) -> Maybe (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v
- IBranch2 :: Depth -> (SomeKey k, ValueCount, Tree d Complete k v) -> (SomeKey k, ValueCount, Tree d Complete k v) -> Map (Key Nonterminal k) (ValueCount, Tree d Complete k v) -> Maybe (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v
- getDepth :: TreeNode n => n k v -> Depth
- getValueCount :: TreeNode n => n k v -> ValueCount
Documentation
type ValueCount = Int Source
Alias that indicates the total number of values underneath a tree
data StableTree k v Source
StableTree
is the user-visible type that wraps the actual Tree
implementation. All the public functions operate on this type.
forall d . StableTree_I (Tree d Incomplete k v) | |
forall d . StableTree_C (Tree d Complete k v) |
(Ord k, StableKey k) => Functor (StableTree k) | |
(Eq k, Eq v) => Eq (StableTree k v) | |
(Ord k, Show k, Show v) => Show (StableTree k v) |
data Incomplete Source
Used to indicate that a Tree
is not complete
data Tree d c k v where Source
The actual B-Tree variant. StableTree is built on one main idea: every
Key
is either Terminal
or Nonterminal
, and every Tree
is Complete
or Incomplete
. A complete Tree
is one whose final element's Key is
terminal, and the rest of the Keys are not (exept for two freebies at the
beginning to guarantee convergence). A complete tree always has complete
children.
If we don't have enough data to generate a complete tree (i.e. we ran out of
elements before hitting a terminal key), then an Incomplete
tree is
generated. Incomplete trees are always contained by other incomplete trees,
and a tree built from only the complete children of an incomplete tree would
never itself be complete.
It is easiest to understand how this structure promotes stability by looking at how trees typically work. The easiest tree to understand is a simple, well balanced, binary tree. In that case, we would have a structure like this:
|D| |B| |F| |A| |C| |E| |G|
Now, suppose that we want to delete the data stored in |A|
. Then, we'll
get a new structure that shares nothing in common with the original one:
|E| |C| |G| |B| |D| |F|
The entire tree had to be re-written. This structure is clearly unstable under mutation. Making the tree wider doesn't help much if the tree's size is changing. Simple updates to existing keys are handled well by branches with many children, but deleting from or adding to the beginning of the tree will always cause every single branch to change, which is what this structure is trying to avoid.
Instead, the stable tree branches have variable child counts. A branch is considered full when its highest key is "terminal", which is determined by hashing the key and looking at some bits of the hash. I've found that a target branch size of 16 children works fairly well, so we check to see if the hash has its least-significant four bits set; if that's the case, the key is terminal. A branch gets two free children (meaning it doesn't care about whether the keys are terminal or not), and then a run of nonterminal keys, and a final, terminal key. Under this scheme, inserting a new entry into a branch will probably mean inserting a nonterminal key, and it will probably be inserted into the run of nonterminal children. If that's the case, no neighbors will be affected, and only the parents will have to change to point to the new branch. Stability is achieved!
getDepth :: TreeNode n => n k v -> Depth Source
Get the depth (height?) of a Tree
or StableTree
getValueCount :: TreeNode n => n k v -> ValueCount Source
Get the total number of key/value pairs stored under this Tree
or
StableTree