Data.StableTree.Types

Definitions of primitive types used in different modules of stable-tree

Documentation

type Depth = Int

Alias to indicate how deep a branch in a tree is. Bottoms have depth 0

type ValueCount = Int

Alias that indicates the total number of values underneath a tree

data StableTree k v

StableTree is the user-visible type that wraps the actual Tree implementation. All the public functions operate on this type.

Constructors

forall d . StableTree_I (Tree d Incomplete k v)

forall d . StableTree_C (Tree d Complete k v)

Instances

Eq (StableTree k v)

Ord (StableTree k v)

(Ord k, Show k, Show v) => Show (StableTree k v)

data Incomplete

Used to indicate that a Tree is not complete

data Complete

Used to indicate that a Tree is complete

data Z

Empty type to indicate a Tree with Zero depth (a bottom node)

data S a

Empty type to indicate a Tree with some known height (a branch)

data Tree d c k v where

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!

Constructors

Bottom :: ObjectID -> (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> (Key Terminal k, v) -> Tree Z Complete k v

IBottom0 :: ObjectID -> Maybe (SomeKey k, v) -> Tree Z Incomplete k v

IBottom1 :: ObjectID -> (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> Tree Z Incomplete k v

Branch :: ObjectID -> 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 :: ObjectID -> Depth -> (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v

IBranch1 :: ObjectID -> 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 :: ObjectID -> 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

Instances

Eq (Tree d c k v)

(Ord k, Show k, Show v) => Show (Tree d c k v)

data Fragment k v

A Fragment is a user-visible part of a tree, i.e. a single node in the tree that can actually be manipulated by a user. This is useful when doing the work of persisting trees, and its serialize instance is also used to calculate Tree ObjectIDs. See toFragments and fromFragments for functions to convert between Fragments and Trees. see store and load for functions related to storing and retrieving Fragments.

Constructors

FragmentBranch

Fields

fragmentDepth :: Depth

fragmentChildren :: Map k (ValueCount, ObjectID)

FragmentBottom

Fields

fragmentMap :: Map k v

Instances

(Eq k, Eq v) => Eq (Fragment k v)

(Ord k, Ord v) => Ord (Fragment k v)

(Show k, Show v) => Show (Fragment k v)

(Ord k, Serialize k, Serialize v) => Serialize (Fragment k v)

mkBottom :: (Ord k, Serialize k, Serialize v) => (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> (Key Terminal k, v) -> Tree Z Complete k v

Helper to create a Bottom instance with a calculated ObjectID

mkIBottom0 :: (Ord k, Serialize k, Serialize v) => Maybe (SomeKey k, v) -> Tree Z Incomplete k v

Helper to create an IBottom0 instance with a calculated ObjectID

mkIBottom1 :: (Ord k, Serialize k, Serialize v) => (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> Tree Z Incomplete k v

Helper to create an IBottom1 instance with a calculated ObjectID

mkBranch :: (Ord k, Serialize k, Serialize v) => 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

Helper to create a Branch instance with a calculated ObjectID

mkIBranch0 :: (Ord k, Serialize k, Serialize v) => Depth -> (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v

Helper to create an IBranch0 instance with a calculated ObjectID

mkIBranch1 :: (Ord k, Serialize k, Serialize v) => Depth -> (SomeKey k, ValueCount, Tree d Complete k v) -> Maybe (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v

Helper to create an IBranch1 instance with a calculated ObjectID

mkIBranch2 :: (Ord k, Serialize k, Serialize v) => 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

Helper to create an IBranch2 instance with a calculated ObjectID

getObjectID :: TreeNode n => n k v -> ObjectID

Get the ObjectID of a Tree or StableTree

getDepth :: TreeNode n => n k v -> Depth

Get the depth (height?) of a Tree or StableTree

getValueCount :: TreeNode n => n k v -> ValueCount

Get the total number of key/value pairs stored under this Tree or StableTree

calcObjectID :: (TreeNode n, Ord k, Serialize k, Serialize v) => n k v -> ObjectID

Do the (expensive) calculation of a Tree or StableTree; generally used to do the initial ObjectID calculation when constructing an instance

fixObjectID :: (TreeNode n, Ord k, Serialize k, Serialize v) => n k v -> n k v

Recalculate the object's ObjectID and return the updated object; pretty much a convenience function around calcObjectID

makeFragment :: (TreeNode n, Ord k) => n k v -> Fragment k v

Get the Fragment representing this exact Tree node, used for persistent storage