Home Reference Source Test
public class | source

LeafNode

Extends:

* → LeafNode

A Leaf Node in the B+Tree.

Constructor Summary

Public Constructor
public

constructor(keys: Array<*>, records: Array<*>)

Creates a new leaf node.

Member Summary

Public Members
public
public
public get

records: Array<*>

Method Summary

Public Methods
public

addKey(key: *, record: *): number

Adds a key, record pair to this leaf node.
public

getItem(key: *, near: BTree.NEAR_MODE): number

Searches the node for a specific key and returns its position if found.
public

isLeaf(): boolean

Returns whether this is a leaf node.
public

merge(frNod: LeafNode, paNod: InnerNode, frKey: *)

Merges two leaf nodes together (this + frNod).
public

Splits the leaf node into two nodes (this + one new node).

Public Constructors

public constructor(keys: Array<*>, records: Array<*>) source

Creates a new leaf node. Leaf nodes store key value pairs, hence the keys and records arrays are required to have the same length. In an index, the keys array usually stores the secondary key, while the records array stores the corresponding primary key. The B+Tree ensures that the items in the keys array are ordered ascending.

Params:

NameTypeAttributeDescription
keys Array<*>
  • optional

Optional array of keys (default is empty).
records Array<*>
  • optional

Optional array of records (default is empty).

Public Members

public nextLeaf: * source

public prevLeaf: * source

public get records: Array<*> source

Public Methods

public addKey(key: *, record: *): number source

Adds a key, record pair to this leaf node. By definition, the key is inserted into the keys of this leaf node, such that the ascending order of the keys is maintained.

Params:

NameTypeAttributeDescription
key *

The key to insert.
record *

The corresponding record to insert.

Return:

number

The position it was inserted at.

public getItem(key: *, near: BTree.NEAR_MODE): number source

Searches the node for a specific key and returns its position if found. The near parameter allows to find either an exact match or the first key greater/less or equal than the specified key.

Since the B+tree limits the number of records per leaf node, the complexity of this method is in O([order/2, order-1]).

Params:

NameTypeAttributeDescription
key *

The key to look for.
near BTree.NEAR_MODE

Return:

number

The index of the match if found, -1 otherwise.

public isLeaf(): boolean source

Returns whether this is a leaf node.

Return:

boolean

True, since it is a leaf node.

public merge(frNod: LeafNode, paNod: InnerNode, frKey: *) source

Merges two leaf nodes together (this + frNod). The given node frNod is no longer connected afterwards.

Params:

NameTypeAttributeDescription
frNod LeafNode

The node to merge with.
paNod InnerNode

The parent node that needs to be updated.
frKey *

The key of the old leaf in the parent.

public split(): LeafNode source

Splits the leaf node into two nodes (this + one new node). The resulting nodes should have almost equal sizes. The new node will return the upper half of the previous entries.

Return:

LeafNode

The new leaf node containing the upper half of entries.