IBTree
Direct Implemented:
This interface describes the general functionality of our B+Tree implementation.
All operations that are expected to return a key-record pair actually only set the pointer in the BTree object. This behaviour is due to the original BTree implementation we based on and is likely to change in future versions.
Member Summary
| Public Members | ||
| public get abstract |
currentKey: * The current key as returned by any operation. |
|
| public get abstract |
The current record as returned by any operation. |
|
| public get abstract |
length: number The total number of records. |
|
Method Summary
| Public Methods | ||
| public abstract |
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 abstract |
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 abstract |
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 abstract |
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 abstract |
goto(cnt: number): boolean Jumps to the cnt entry starting from the smallest key (i.e., leftmost leaf, first entry) if cnt > 0. |
|
| public abstract |
insert(key: *, rec: *): boolean Inserts a new key-record pair into the BTree, if there is no entry for that key. |
|
| public abstract |
keynum(): number Returns the index of the current entry (key/record) in a sorted list of all entries. |
|
| public abstract |
pack(): boolean Rebuilds/balances the whole tree. |
|
| public abstract |
remove(key: *): boolean Removes a key-record pair from the BTree. |
|
| public abstract |
seek(key: *, near: BTree.NEAR_MODE): boolean Searches the tree for a specific key and advances the current key/record pointers if found. |
|
| public abstract |
skip(cnt: number): boolean Advances the current key/record pointers by a given number of steps. |
|
Public Members
public get abstract currentKey: * source
The current key as returned by any operation. It is null if there is no matching record.
public get abstract currentRecord: * source
The current record as returned by any operation. It is null if there is no matching record.
public get abstract 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 abstract 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 abstract 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 abstract 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 abstract 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 abstract 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 abstract 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 abstract 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 abstract 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 abstract 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 abstract 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 abstract 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. |