Class: BPlusTree

BPlusTree(options)

Class representing a B+ Tree.

Constructor

new BPlusTree(options)

Parameters:
Name Type Description
options Object
Properties
Name Type Attributes Default Description
order number <optional>
6

The tree order (or branching factor or node capacity)

debug boolean <optional>
false

Check tree invariants after each insert / remove

cmpFn string <optional>
numericComparison

Comparison function to use

Source:

Methods

check(options) → {boolean}

Check tree invariants

Parameters:
Name Type Description
options Object
Properties
Name Type Attributes Default Description
root BPTree.tree <optional>
this.tree

Tree to check

Source:
Returns:

Returns true or throws an Error()

Type
boolean

depth(options) → {number}

Get tree depth (or height)

Parameters:
Name Type Description
options Object
Properties
Name Type Attributes Default Description
root BPTree.tree <optional>
this.tree

Tree to use

Source:
Returns:

Computed depth

Type
number

fetch(key, options) → {Value|Array.<Value>|Leaf|Object|Boolean}

Fetch the value(s) stored at key.

  • getLeaf returns the whole leaf
  • getPath returns the path from the root to this leaf
  • when defined, notFound can be either 'left' or 'right', it controls which key to return when it wasn't found
Parameters:
Name Type Description
key Key
options Object
Properties
Name Type Attributes Default Description
root BPTree.tree <optional>
this.tree

Tree to search in

getLeaf boolean <optional>
false

Return the leaf containing the value(s)

getPath boolean <optional>
false

Return {val: value(s), leaf: leaf, path: pathFromRootToLeaf}

notFound string <optional>

either 'left' or 'right' - Return what was found left or right from key which doesn't exist

Source:
Returns:
Type
Value | Array.<Value> | Leaf | Object | Boolean

fetchRange(lowerBound, upperBound, options) → {Array.<Values>}

Get all values between keys lowerBound and upperBound

Parameters:
Name Type Description
lowerBound number
upperBound number
options Object
Properties
Name Type Attributes Default Description
descending boolean <optional>
false

Get it reversed (only works if options.keys or options.values)

Source:
Returns:

A flat array of values, or empty array.

Type
Array.<Values>

remove(key, valuenullable) → {Value}

Remove value from key key, or remove key and its value if key only has one value

Parameters:
Name Type Attributes Description
key Key
value Value <nullable>
Source:
Returns:

The removed value

Type
Value

repr(options) → {Object|Array.<Keys>|Array.<Values>}

Get a {k1: v1, k2: v2, ...} object representing the stored data

Parameters:
Name Type Description
options Object
Properties
Name Type Attributes Default Description
root BPTree.tree <optional>
this.tree

Tree to check

getKeys boolean <optional>
false

Instead of an object, get a list of all keys

getValues boolean <optional>
false

Instead of an object, get a list of all values

descending boolean <optional>
false

Get it reversed (only works if options.getKeys or options.getValues)

Source:
Returns:
Type
Object | Array.<Keys> | Array.<Values>

store(key, value) → {boolean}

Insert value at key key

Parameters:
Name Type Description
key Key
value Value
Source:
Returns:

true

Type
boolean

(generator) values(options) → {Generator}

Tree values generator. It will start generating values from a certain key until the end of the tree OR until target is found OR until limit is reached OR until there are no elements anymore.

In other words:

  • if target is found before limit, it'll stop
  • if limit is reached before target was found, it'll stop
  • target and limit are both optional: use none of them, one of them, or both
  • keyNotFound is optional, it lets you decide which key to prefer when the key is not found
Parameters:
Name Type Description
options Object
Properties
Name Type Attributes Description
key Key <optional>

Key at which to start generating.

target boolean <optional>

Stop generating when this value is found.

limit number <optional>

Generate at max this number of values.

keyNotFound string <optional>

See notFound of BPlusTree.fetch

Source:
Returns:
  • e.g. { value: { k: 6, v: ['f', 'g'] }, done: false }
Type
Generator