Constructor Summary
Public Constructor | ||
public |
constructor(order: number) Creates a new BTree of a given order. |
Member Summary
Public Members | ||
public get |
currentKey: * The current key as returned by any operation. |
|
public get |
The current record as returned by any operation. |
|
public get |
length: number The total number of records. |
Method Summary
Public Methods | ||
public |
goBottom(): boolean Jumps to the largest key's entry (i.e., rightmost leaf, last entry). False will only be returned if the tree is completely empty. |
|
public |
goToLowerBound(lower: *, lowerOpen: boolean): boolean Advances to the smallest key k', such that either k' > lower (if lowerOpen) or k' ≥ lower (if !lowerOpen). If lower is undefined, jump to the smallest key's entry. |
|
public |
goToUpperBound(upper: *, upperOpen: boolean): boolean Advances to the largest key k', such that either k' < upper (if upperOpen) or k' ≤ upper (if !upperOpen). If upper is undefined, jump to the largest key's entry. |
|
public |
goTop(): boolean Jumps to the smallest key's entry (i.e., leftmost leaf, first entry). False will only be returned if the tree is completely empty. |
|
public |
goto(cnt: number): boolean Jumps to the cnt entry starting from the smallest key (i.e., leftmost leaf, first entry) if cnt > 0. |
|
public |
insert(key: *, rec: *): boolean Inserts a new key-record pair into the BTree, if there is no entry for that key. |
|
public |
keynum(): number Returns the index of the current entry (key/record) in a sorted list of all entries. |
|
public |
pack(): boolean Rebuilds/balances the whole tree. |
|
public |
remove(key: *): boolean Removes a key-record pair from the BTree. |
|
public |
seek(key: *, near: BTree.NEAR_MODE): boolean Searches the tree for a specific key and advances the current key/record pointers if found. |
|
public |
skip(cnt: number): boolean Advances the current key/record pointers by a given number of steps. |
Public Constructors
public constructor(order: number) source
Creates a new BTree of a given order. The order specifies how many entries a single node can contain. A leaf node generally contains [order/2, order-1] entries, while an inner node contains [(order-1)/2, order-1] entries.
Params:
Name | Type | Attribute | Description |
order | number | The order of the tree. |
Public Members
public get currentKey: * source
The current key as returned by any operation. It is null if there is no matching record.
public get currentRecord: * source
The current record as returned by any operation. It is null if there is no matching record.
public get length: number source
The total number of records. Note that if the record is a list/set of records, these are not counted.
Public Methods
public goBottom(): boolean source
Jumps to the largest key's entry (i.e., rightmost leaf, last entry). False will only be returned if the tree is completely empty.
Return:
boolean | True if there is such an entry, false otherwise. |
public goToLowerBound(lower: *, lowerOpen: boolean): boolean source
Advances to the smallest key k', such that either k' > lower (if lowerOpen) or k' ≥ lower (if !lowerOpen). If lower is undefined, jump to the smallest key's entry.
Params:
Name | Type | Attribute | Description |
lower | * | A lower bound on the key or undefined. |
|
lowerOpen | boolean |
|
Whether lower may be included or not. |
Return:
boolean | True if there is such an entry, false otherwise. |
public goToUpperBound(upper: *, upperOpen: boolean): boolean source
Advances to the largest key k', such that either k' < upper (if upperOpen) or k' ≤ upper (if !upperOpen). If upper is undefined, jump to the largest key's entry.
Params:
Name | Type | Attribute | Description |
upper | * | An upper bound on the key or undefined. |
|
upperOpen | boolean |
|
Whether upper may be included or not. |
Return:
boolean | True if there is such an entry, false otherwise. |
public goTop(): boolean source
Jumps to the smallest key's entry (i.e., leftmost leaf, first entry). False will only be returned if the tree is completely empty.
Return:
boolean | True if there is such an entry, false otherwise. |
public goto(cnt: number): boolean source
Jumps to the cnt entry starting from the smallest key (i.e., leftmost leaf, first entry) if cnt > 0. If cnt < 0, it jumps to the cnt entry starting from the largest key (i.e., rightmost leaf, last entry).
Params:
Name | Type | Attribute | Description |
cnt | number |
|
The record to jump to (may be negative). |
Return:
boolean | True if there is a record to jump to, false otherwise. |
public insert(key: *, rec: *): boolean source
Inserts a new key-record pair into the BTree, if there is no entry for that key. The current record and current key are set to the new entry in case of success or the existing entry if present.
Params:
Name | Type | Attribute | Description |
key | * | The unique key for the record. |
|
rec | * | The record associated with the key. |
Return:
boolean | True if the record was inserted, false if there was already a record with that key. |
public keynum(): number source
Returns the index of the current entry (key/record) in a sorted list of all entries. For the B+ Tree, this is done by traversing the leafs from the leftmost leaf, first entry until the respective key is found.
Return:
number | The entry position. |
public pack(): boolean source
Rebuilds/balances the whole tree. Inserting and deleting keys into a tree will result in some leaves and nodes having the minimum number of keys allowed. This routine will ensure that each leaf and node has as many keys as possible, resulting in a denser, flatter tree. False is only returned if the tree is completely empty.
Return:
boolean | True if the tree is not completely empty. |
public remove(key: *): boolean source
Removes a key-record pair from the BTree. In case of successful deletion, the current record and key will be set to the next entry greater or equal. If no record was found, they will be reset to null.
Params:
Name | Type | Attribute | Description |
key | * | The unique key for the record. |
Return:
boolean | True if the record was deleted, false if there is no such record. |
public seek(key: *, near: BTree.NEAR_MODE): boolean source
Searches the tree for a specific key and advances the current key/record pointers if found. By default only an exact key match is found, but the near parameter also allows to advance to the next entry greater/less or equal than the specified key.
Params:
Name | Type | Attribute | Description |
key | * | The key to look for. |
|
near | BTree.NEAR_MODE |
|
Optional parameter, specifies to look for a key k' =/≤/≥ key. |
Return:
boolean | True if such a key was found, false otherwise. |
public skip(cnt: number): boolean source
Advances the current key/record pointers by a given number of steps. Default is advancing by 1, which means the next record (the new key will thus be the next larger key). -1 means the previous record (the new key will thus be the next smaller key).
Params:
Name | Type | Attribute | Description |
cnt | number |
|
The number of records to advance (may be negative). |
Return:
boolean | True if there is a record to advance to, false otherwise. |