Skip to content

Instantly share code, notes, and snippets.

@KartikBazzad

KartikBazzad/BPlusTree.ts

Last active February 16, 2025 16:39
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save KartikBazzad/211d0e5a1ed1961d809c13a90859284d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save KartikBazzad/211d0e5a1ed1961d809c13a90859284d to your computer and use it in GitHub Desktop.
Download ZIP
BPlusTree Implementation
Raw
BPlusTree.ts
export class BPlusTreeNode<T> {
is_leaf: boolean;
keys: number[];
children: BPlusTreeNode<T>[];
values: T[];
next_leaf: BPlusTreeNode<T> | null;
constructor(
is_leaf: boolean,
keys: number[],
values: T[],
children: BPlusTreeNode<T>[],
next_leaf: BPlusTreeNode<T> | null
) {
this.is_leaf = is_leaf;
this.keys = keys;
this.values = values;
this.children = children;
this.next_leaf = next_leaf;
}
_insert_into_node(key: number, value: T) {
const index = this.keys.findIndex((k) => k >= key);
if (index !== -1 && this.keys[index] === key) {
this.values[index] = value; // Update existing value
} else {
this.keys.splice(index === -1 ? this.keys.length : index, 0, key);
this.values.splice(index === -1 ? this.values.length : index, 0, value);
}
}
toJSON(): any {
return {
is_leaf: this.is_leaf,
keys: this.keys,
values: this.is_leaf ? this.values : undefined, // Store values only in leaf nodes
children: this.is_leaf
? undefined
: this.children.map((child) => child.toJSON()), // Store children for internal nodes
next_leaf: this.is_leaf && this.next_leaf ? this.next_leaf.keys[0] : null, // Store reference to next leaf (by first key)
};
}
/** Load node from JSON */
static fromJSON<T>(
data: any,
nodeMap: Map<number, BPlusTreeNode<T>>
): BPlusTreeNode<T> {
const node = new BPlusTreeNode<T>(
data.is_leaf,
data.keys,
data.values || [],
[],
nodeMap.get(data.next_leaf) || null
);
nodeMap.set(data.keys[0] || 0, node);
if (!data.is_leaf && data.children) {
node.children = data.children.map((childData: any) =>
BPlusTreeNode.fromJSON<T>(childData, nodeMap)
);
}
return node;
}
}
export class BPlusTree<T> {
root: BPlusTreeNode<T>;
degree: number;
constructor(degree: number) {
this.root = new BPlusTreeNode<T>(true, [], [], [], null);
this.degree = degree;
}
insert(key: number, value: T) {
const [new_root, new_key] = this._insert_into_node(this.root, key, value);
if (new_root && new_key !== null) {
this.root = new BPlusTreeNode<T>(
false,
[new_key],
[],
[this.root, new_root],
null
);
}
}
private _insert_into_node(
node: BPlusTreeNode<T>,
key: number,
value: T
): [BPlusTreeNode<T> | null, number | null] {
if (node.is_leaf) {
node._insert_into_node(key, value);
if (node.keys.length > this.degree) {
return this._split_leaf_node(node);
}
} else {
const index = this._find_child_index(node.keys, key);
const [new_child, new_key] = this._insert_into_node(
node.children[index],
key,
value
);
if (new_child && new_key !== null) {
node.keys.splice(index, 0, new_key);
node.children.splice(index + 1, 0, new_child);
if (node.keys.length > this.degree) {
return this._split_internal_node(node);
}
}
}
return [null, null];
}
private _split_internal_node(
node: BPlusTreeNode<T>
): [BPlusTreeNode<T>, number] {
const mid = Math.floor(this.degree / 2);
const new_keys = node.keys.slice(mid + 1);
const new_children = node.children.slice(mid + 1);
const promoted_key = node.keys[mid]; // Correctly promote middle key
const new_node = new BPlusTreeNode<T>(
false,
new_keys,
[],
new_children,
null
);
node.keys = node.keys.slice(0, mid); // Remove promoted key from left node
node.children = node.children.slice(0, mid + 1);
return [new_node, promoted_key];
}
private _split_leaf_node(node: BPlusTreeNode<T>): [BPlusTreeNode<T>, number] {
const mid = Math.ceil(this.degree / 2); // Ensuring balanced split
const new_keys = node.keys.slice(mid);
const new_values = node.values.slice(mid);
const new_node = new BPlusTreeNode<T>(
true,
new_keys,
new_values,
[],
node.next_leaf
);
node.keys = node.keys.slice(0, mid);
node.values = node.values.slice(0, mid);
node.next_leaf = new_node;
return [new_node, new_keys[0]];
}
search(key: number): T | undefined {
return this._search(this.root, key);
}
private _search(node: BPlusTreeNode<T> | null, key: number): T | undefined {
if (node === null) {
return undefined;
}
if (node.is_leaf) {
const index = node.keys.indexOf(key);
return index !== -1 ? node.values[index] : undefined;
} else {
const index = this._find_child_index(node.keys, key);
return this._search(node.children[index], key);
}
}
private _find_child_index(keys: number[], key: number): number {
let low = 0,
high = keys.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (keys[mid] === key) return mid + 1; // Ensure correct placement
if (keys[mid] < key) low = mid + 1;
else high = mid - 1;
}
return low;
}
delete(key: number) {
this._delete(this.root, key);
}
private _delete(node: BPlusTreeNode<T>, key: number): void {
if (node.is_leaf) {
// Delete key from leaf node
const index = node.keys.indexOf(key);
if (index !== -1) {
node.keys.splice(index, 1);
node.values.splice(index, 1);
}
} else {
const index = this._find_child_index(node.keys, key);
if (index < node.keys.length && node.keys[index] === key) {
// Case: Key exists in internal node
this._delete_internal(node, index);
} else {
// Case: Key does not exist in internal node, recurse on child
this._delete(node.children[index], key);
// Handle underflow in child
if (node.children[index].keys.length < Math.ceil(this.degree / 2)) {
this._fix_underflow(node, index);
}
}
}
}
// Handles deletion in an internal node
private _delete_internal(node: BPlusTreeNode<T>, index: number): void {
const left_child = node.children[index];
const right_child = node.children[index + 1];
if (left_child.keys.length >= Math.ceil(this.degree / 2)) {
// Replace key with predecessor (max key in left child)
const predecessor_key = left_child.keys[left_child.keys.length - 1];
const predecessor_value = left_child.values[left_child.values.length - 1];
node.keys[index] = predecessor_key;
this._delete(left_child, predecessor_key);
} else if (right_child.keys.length >= Math.ceil(this.degree / 2)) {
// Replace key with successor (min key in right child)
const successor_key = right_child.keys[0];
const successor_value = right_child.values[0];
node.keys[index] = successor_key;
this._delete(right_child, successor_key);
} else {
// Merge left_child and right_child
this._merge_nodes(node, index);
}
}
// Handles underflow by borrowing or merging
private _fix_underflow(node: BPlusTreeNode<T>, index: number): void {
const child = node.children[index];
// Try borrowing from left sibling
if (
index > 0 &&
node.children[index - 1].keys.length > Math.ceil(this.degree / 2)
) {
this._borrow_from_left(node, index);
}
// Try borrowing from right sibling
else if (
index < node.children.length - 1 &&
node.children[index + 1].keys.length > Math.ceil(this.degree / 2)
) {
this._borrow_from_right(node, index);
}
// Merge if borrowing isn't possible
else {
if (index > 0) {
this._merge_nodes(node, index - 1);
} else {
this._merge_nodes(node, index);
}
}
}
// Borrows a key from the left sibling
private _borrow_from_left(node: BPlusTreeNode<T>, index: number): void {
const child = node.children[index];
const left_sibling = node.children[index - 1];
// Move separator key down
child.keys.unshift(node.keys[index - 1]);
if (!child.is_leaf) {
child.children.unshift(left_sibling.children.pop()!);
} else {
child.values.unshift(left_sibling.values.pop()!);
}
// Move max key from left sibling up
node.keys[index - 1] = left_sibling.keys.pop()!;
}
// Borrows a key from the right sibling
private _borrow_from_right(node: BPlusTreeNode<T>, index: number): void {
const child = node.children[index];
const right_sibling = node.children[index + 1];
// Move separator key down
child.keys.push(node.keys[index]);
if (!child.is_leaf) {
child.children.push(right_sibling.children.shift()!);
} else {
child.values.push(right_sibling.values.shift()!);
}
// Move min key from right sibling up
node.keys[index] = right_sibling.keys.shift()!;
}
// Merges a child node with its sibling
private _merge_nodes(node: BPlusTreeNode<T>, index: number): void {
const left_child = node.children[index];
const right_child = node.children[index + 1];
// Merge key from parent into left child
left_child.keys.push(node.keys[index]);
left_child.keys.push(...right_child.keys);
left_child.values.push(...right_child.values);
if (!left_child.is_leaf) {
left_child.children.push(...right_child.children);
}
left_child.next_leaf = right_child.next_leaf;
// Remove right child
node.keys.splice(index, 1);
node.children.splice(index + 1, 1);
// Handle root shrinking
if (node === this.root && node.keys.length === 0) {
this.root = left_child;
}
}
toJSON(): string {
return JSON.stringify(
{
degree: this.degree,
root: this.root.toJSON(),
},
null,
2
);
}
/** Load B+ tree from JSON */
static fromJSON<T>(json: string): BPlusTree<T> {
const data = JSON.parse(json);
const tree = new BPlusTree<T>(data.degree);
const nodeMap = new Map<number, BPlusTreeNode<T>>();
tree.root = BPlusTreeNode.fromJSON<T>(data.root, nodeMap);
// Reconnect leaf nodes based on stored next_leaf references
for (const [key, node] of nodeMap) {
if (node.is_leaf && node.next_leaf !== null) {
node.next_leaf = nodeMap.get(node.next_leaf as any) || null;
}
}
return tree;
}
}
export default BPlusTree;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment