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.

Index

Constructors

constructor

Methods

ascending at compareKeys deleteAt descending find first get getCount insert isValid last merge moveNext movePrior next prior range updateAt upsert

Constructors

constructor

new BTree<TKey, TEntry>(
keyFromEntry?: (entry: TEntry) => TKey,
compare?: (a: TKey, b: TKey) => number,
): BTree<TKey, TEntry>
Type Parameters
- TKey
- TEntry
Parameters
- OptionalkeyFromEntry: (entry: TEntry) => TKey = ...
  a function to extract the key from an entry. The default assumes the key is the entry itself.
- Optionalcompare: (a: TKey, b: TKey) => number = ...
  a comparison function for keys. The default uses < and > operators.
Returns BTree<TKey, TEntry>
- Defined in b-tree.ts:22

Methods

ascending

ascending(path: Path<TKey, TEntry>): 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
- path: Path<TKey, TEntry>
Returns IterableIterator<Path<TKey, TEntry>>
- Defined in b-tree.ts:176

at

at(path: Path<TKey, TEntry>): undefined | TEntry
Parameters
- path: Path<TKey, TEntry>
Returns undefined | TEntry
the entry for the given path if on an entry; undefined otherwise.
- Defined in b-tree.ts:54

`Protected`compareKeys

compareKeys(a: TKey, b: TKey): 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
- a: TKey
- b: TKey
Returns number
- Defined in b-tree.ts:243

deleteAt

deleteAt(path: Path<TKey, TEntry>): boolean
Deletes the entry at the given path. The on property of the path will be cleared.
Parameters
- path: Path<TKey, TEntry>
Returns boolean
true if the delete succeeded (the key was found); false otherwise.
- Defined in b-tree.ts:164

descending

descending(path: Path<TKey, TEntry>): 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
- path: Path<TKey, TEntry>
Returns IterableIterator<Path<TKey, TEntry>>
- Defined in b-tree.ts:184

find

find(key: TKey): Path<TKey, TEntry>
Attempts to find the given key
Parameters
- key: TKey
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.
- Defined in b-tree.ts:42

first

first(): Path<TKey, TEntry>
Returns Path<TKey, TEntry>
a path to the first entry (on = false if no entries)
- Defined in b-tree.ts:30

get

get(key: TKey): 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
- key: TKey
Returns undefined | TEntry
the entry for the given key if found; undefined otherwise.
- Defined in b-tree.ts:49

getCount

getCount(from?: { ascending?: boolean; path: Path<TKey, TEntry> }): number
Computed (not stored) count. Computes the sum using leaf-node lengths. O(n/af) where af is average fill.
Parameters
- Optionalfrom: { 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
- Defined in b-tree.ts:193

insert

insert(entry: TEntry): 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
- entry: TEntry
Returns Path<TKey, TEntry>
path to the new (on = true) or conflicting (on = false) row.
- Defined in b-tree.ts:94

isValid

isValid(path: Path<TKey, TEntry>): boolean
Parameters
- path: Path<TKey, TEntry>
Returns boolean
true if the given path remains valid; false if the tree has been mutated, invalidating the path.
- Defined in b-tree.ts:86

last

last(): Path<TKey, TEntry>
Returns Path<TKey, TEntry>
a path to the last entry (on = false if no entries)
- Defined in b-tree.ts:35

merge

merge(
newEntry: TEntry,
getUpdated: (existing: TEntry) => TEntry,
): [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) => 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.
- Defined in b-tree.ts:143

moveNext

moveNext(path: Path<TKey, TEntry>): void
Attempts to advance the given path one step forward. (mutates the path)
Parameters
- path: Path<TKey, TEntry>
Returns void
- Defined in b-tree.ts:220

movePrior

movePrior(path: Path<TKey, TEntry>): void
Attempts to advance the given path one step backwards. (mutates the path)
Parameters
- path: Path<TKey, TEntry>
Returns void
- Defined in b-tree.ts:233

next(path: Path<TKey, TEntry>): Path<TKey, TEntry>
Parameters
- path: Path<TKey, TEntry>
Returns Path<TKey, TEntry>
a path one step forward. on will be true if the path hasn't hit the end.
- Defined in b-tree.ts:213

prior

prior(path: Path<TKey, TEntry>): Path<TKey, TEntry>
Parameters
- path: Path<TKey, TEntry>
Returns Path<TKey, TEntry>
a path one step backward. on will be true if the path hasn't hit the end.
- Defined in b-tree.ts:226

range

range(range: KeyRange<TKey>): IterableIterator<Path<TKey, TEntry>>
Iterates based on the given range WARNING: mutation during iteration will result in an exception
Parameters
- range: KeyRange<TKey>
Returns IterableIterator<Path<TKey, TEntry>>
- Defined in b-tree.ts:62

updateAt

updateAt(
path: Path<TKey, TEntry>,
newEntry: TEntry,
): [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
- path: Path<TKey, TEntry>
- newEntry: TEntry
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
- Defined in b-tree.ts:111

upsert

upsert(entry: TEntry): 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
- entry: TEntry
Returns Path<TKey, TEntry>
path to the new entry. on = true if existing; on = false if new.
- Defined in b-tree.ts:126

Class BTree<TKey, TEntry>

Type Parameters

Index

Constructors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns BTree<TKey, TEntry>

Methods

ascending

Parameters

Returns IterableIterator<Path<TKey, TEntry>>

at

Parameters

Returns undefined | TEntry

ProtectedcompareKeys

Parameters

Returns number

deleteAt

Parameters

Returns boolean

descending

Parameters

Returns IterableIterator<Path<TKey, TEntry>>

find

Parameters

Returns Path<TKey, TEntry>

first

Returns Path<TKey, TEntry>

get

Parameters

Returns undefined | TEntry

getCount

Parameters

Returns number

insert

Parameters

Returns Path<TKey, TEntry>

isValid

Parameters

Returns boolean

last

Returns Path<TKey, TEntry>

merge

Parameters

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

moveNext

Parameters

Returns void

movePrior

Parameters

Returns void

next

Parameters

Returns Path<TKey, TEntry>

prior

Parameters

Returns Path<TKey, TEntry>

range

Parameters

Returns IterableIterator<Path<TKey, TEntry>>

updateAt

Parameters

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

upsert

Parameters

Returns Path<TKey, TEntry>

Settings

On This Page

`Protected`compareKeys