public class | source

InnerNode

Extends:

* → InnerNode

An Inner Node in the B+Tree.

Constructor Summary

Public Constructor
public	constructor(keys: Array<*>, nodePointers: Array<Node>) Creates a new inner node.

Member Summary

Public Members
public get	nodePointers: Array<Node>

Method Summary

Public Methods
public	addKey(key: *, ptrL: Node, ptrR: Node): number Adds a key corresponding to a new child node to this inner node.
public	getItem(key: *): number Searches the node for a specific key and returns the matching child's position. Since the B+tree limits the number of records per leaf node, the complexity of this method is in O([(order-1)/2, order-1]).
public	isLeaf(): boolean Returns whether this is a leaf node.
public	merge(frNod: InnerNode, paNod: InnerNode, paItm: number): * Merges two inner nodes together (this + frNod).
public	split(): InnerNode Splits the node into two nodes (this + one new node).

Public Constructors

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

Creates a new inner node. The only key values that appear in the internal nodes are the first key values from each leaf, with the exception of the key from the very first leaf which isn't included. Each key value that appears in the internal nodes only appears once.

Params:

Name	Type	Attribute	Description
keys	Array<*>	optional	The first key of each child node (except for the first one).
nodePointers	Array<Node>	optional	The pointers to the child nodes.

Public Members

public get nodePointers: Array<Node> source

Public Methods

public addKey(key: *, ptrL: Node, ptrR: Node): number source

Adds a key corresponding to a new child node to this inner 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:

Name	Type	Attribute	Description
key	*		The key to insert.
ptrL	Node		The pointer to the corresponding child node.
ptrR	Node		The pointer to the node right of the child node.

Return:

number

The position it was inserted at.

public getItem(key: *): number source

Searches the node for a specific key and returns the matching child's position.

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

Params:

Name	Type	Attribute	Description
key	*		The key to look for.

Return:

number

The index of the match.

public isLeaf(): boolean source

Returns whether this is a leaf node.

Return:

boolean

False, since it is an inner node.

public merge(frNod: InnerNode, paNod: InnerNode, paItm: number): * source

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

Params:

Name	Type	Attribute	Description
frNod	InnerNode		The node to merge with.
paNod	InnerNode		The parent node that needs to be updated.
paItm	number		The position in the parent.

Return:

public split(): InnerNode source

Splits the 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:

InnerNode

The new inner node containing the upper half of entries.