Class BTree<TKey, TEntry>

Represents a lightweight B+(ish)Tree (data at leaves, but no linked list of leaves). Allows for efficient storage and retrieval of data in a sorted manner.

Type Parameters

  • TKey

    The type of keys used for indexing the entries. This might be an element of TEntry, or TEntry itself.

  • TEntry

    The type of entries stored in the B-tree.

Constructors

constructor

Properties

_root _version compare keyFromEntry

Methods

ascending at branchInsert compareKeys deleteAt descending find findFirst findLast first get getCount getFirst getLast getPath indexOfEntry indexOfKey insert internalAscending internalDelete internalDescending internalInsert internalInsertAt internalNext internalPrior internalUpdate isValid last leafInsert merge moveNext movePrior moveToFirst moveToLast next prior range rebalanceBranch rebalanceLeaf updateAt updatePartition upsert validatePath

Constructors

constructor

  • new BTree<TKey, TEntry>(keyFromEntry?, compare?): BTree<TKey, TEntry>

  • Type Parameters

    • TKey
    • TEntry

    Parameters

    • Optional keyFromEntry: ((entry) => TKey) = ...

      a function to extract the key from an entry. The default assumes the key is the entry itself.

    • Optional compare: ((a, b) => number) = ...

      a comparison function for keys. The default uses < and > operators.

        • (a, b): number

        • Parameters

          Returns number

    Returns BTree<TKey, TEntry>

Properties

Private _root

_root: ITreeNode

Private _version

_version: number = 0

Private Readonly compare

compare: ((a, b) => number) = ...

a comparison function for keys. The default uses < and > operators.

Type declaration

    • (a, b): number

    • Parameters

      Returns number

Private Readonly keyFromEntry

keyFromEntry: ((entry) => TKey) = ...

a function to extract the key from an entry. The default assumes the key is the entry itself.

Type declaration

Methods

ascending

  • ascending(path): IterableIterator<Path<TKey, TEntry>>

  • Iterates forward starting from the path location (inclusive) to the end. WARNING: mutation during iteration will result in an exception.

    Parameters

    Returns IterableIterator<Path<TKey, TEntry>>

at

Private branchInsert

Protected compareKeys

  • compareKeys(a, b): number

  • Invokes user-provided comperator to compare two keys. Inner-loop code, so this doesn't do backflips to iron out ES's idiosyncrasies (undefined quirks, infinity, nulls, etc.), but does ensure deterministic comparison. If you want to eak out more performance at the risk of corruption, you can override this method and omit the consistency check.

    Parameters

    Returns number

deleteAt

  • deleteAt(path): boolean

  • Deletes the entry at the given path. The on property of the path will be cleared.

    Parameters

    Returns boolean

    true if the delete succeeded (the key was found); false otherwise.

descending

  • descending(path): IterableIterator<Path<TKey, TEntry>>

  • Iterates backward starting from the path location (inclusive) to the end. WARNING: mutation during iteration will result in an exception

    Parameters

    Returns IterableIterator<Path<TKey, TEntry>>

find

  • find(key): Path<TKey, TEntry>

  • Attempts to find the given key

    Parameters

    Returns Path<TKey, TEntry>

    Path to the key or the "crack" before it. If on is true on the resulting path, the key was found. If on is false, next() and prior() can attempt to move to the nearest match.

Private findFirst

Private findLast

first

get

  • get(key): undefined | TEntry

  • Retrieves the entry for the given key. Use find instead for a path to the key, the nearest match, or as a basis for navigation.

    Parameters

    Returns undefined | TEntry

    the entry for the given key if found; undefined otherwise.

getCount

  • getCount(from?): number

  • Computed (not stored) count. Computes the sum using leaf-node lengths. O(n/af) where af is average fill.

    Parameters

    • Optional from: {
          ascending?: boolean;
          path: Path<TKey, TEntry>;
      }

      if provided, the count will start from the given path (inclusive). If ascending is false, the count will start from the end of the tree. Ascending is true by default.

    Returns number

Private getFirst

Private getLast

Private getPath

Private indexOfEntry

  • indexOfEntry(entries, key): [on: boolean, index: number]

  • Parameters

    Returns [on: boolean, index: number]

Private indexOfKey

insert

  • insert(entry): Path<TKey, TEntry>

  • Adds a value to the tree. Be sure to check the result, as the tree does not allow duplicate keys. Added entries are frozen to ensure immutability

    Parameters

    Returns Path<TKey, TEntry>

    path to the new (on = true) or conflicting (on = false) row.

Private internalAscending

Private internalDelete

Private internalDescending

Private internalInsert

Private internalInsertAt

Private internalNext

Private internalPrior

Private internalUpdate

isValid

  • isValid(path): boolean

  • Parameters

    Returns boolean

    true if the given path remains valid; false if the tree has been mutated, invalidating the path.

last

Private leafInsert

merge

  • merge(newEntry, getUpdated): [path: Path<TKey, TEntry>, wasUpdate: boolean]

  • Inserts or updates depending on the existence of the given key, using callbacks to generate the new value.

    Parameters

    • newEntry: TEntry

      the new entry to insert if the key doesn't exist.

    • getUpdated: ((existing) => TEntry)

      a callback to generate an updated entry if the key does exist. WARNING: mutation in this callback will cause merge to error.

    Returns [path: Path<TKey, TEntry>, wasUpdate: boolean]

    path to new entry and whether an update or insert attempted. If getUpdated callback returns a row that is already present, the resulting path will not be on.

moveNext

  • moveNext(path): void

  • Attempts to advance the given path one step forward. (mutates the path)

    Parameters

    Returns void

movePrior

  • movePrior(path): void

  • Attempts to advance the given path one step backwards. (mutates the path)

    Parameters

    Returns void

Private moveToFirst

  • moveToFirst(node, path): void

  • Starting from the given node, recursively working down to the leaf, build onto the path based on the beginning-most entry.

    Parameters

    Returns void

Private moveToLast

  • moveToLast(node, path): void

  • Starting from the given node, recursively working down to the leaf, build onto the path based on the end-most entry.

    Parameters

    Returns void

next

prior

range

Private rebalanceBranch

  • rebalanceBranch(path, depth): undefined | ITreeNode

  • Parameters

    Returns undefined | ITreeNode

Private rebalanceLeaf

  • rebalanceLeaf(path, depth): undefined | ITreeNode

  • Parameters

    Returns undefined | ITreeNode

updateAt

  • updateAt(path, newEntry): [path: Path<TKey, TEntry>, wasUpdate: boolean]

  • Updates the entry at the given path to the given value. Deletes and inserts if the key changes.

    Parameters

    Returns [path: Path<TKey, TEntry>, wasUpdate: boolean]

    path to resulting entry and whether it was an update (as opposed to an insert). * on = true if update/insert succeeded. * wasUpdate = true if updated; false if inserted. * Returned path is on entry * on = false if update/insert failed. * wasUpdate = true, given path is not on an entry * else newEntry's new key already present; returned path is "near" existing entry

Private updatePartition

  • updatePartition(nodeIndex, path, depth, newKey): void

  • Parameters

    Returns void

upsert

  • upsert(entry): Path<TKey, TEntry>

  • Inserts the entry if it doesn't exist, or updates it if it does. The entry is frozen to ensure immutability.

    Parameters

    Returns Path<TKey, TEntry>

    path to the new entry. on = true if existing; on = false if new.

Private validatePath

Settings

Member Visibility

Theme

On This Page

constructor_root_versioncomparekeyFromEntryascendingatbranchInsertcompareKeysdeleteAtdescendingfindfindFirstfindLastfirstgetgetCountgetFirstgetLastgetPathindexOfEntryindexOfKeyinsertinternalAscendinginternalDeleteinternalDescendinginternalInsertinternalInsertAtinternalNextinternalPriorinternalUpdateisValidlastleafInsertmergemoveNextmovePriormoveToFirstmoveToLastnextpriorrangerebalanceBranchrebalanceLeafupdateAtupdatePartitionupsertvalidatePath

Generated using TypeDoc