B-Trees & B+ Trees

class BTreeNode:
    """A single node in a B-Tree.
    
    Each node stores:
    - keys: sorted list of keys (at most 2t-1 keys)
    - children: child pointers (at most 2t children for internal nodes)
    - leaf: boolean indicating whether this is a leaf node
    """
    def __init__(self, leaf=True):
        self.keys = []       # Sorted list of keys
        self.children = []   # Child pointers (len = len(keys) + 1 for internal nodes)
        self.leaf = leaf     # Leaf nodes have no children

class BTree:
    """B-Tree of minimum degree t.
    
    Each node holds between t-1 and 2t-1 keys.
    Each internal node has between t and 2t children.
    
    Common degree values:
    - t=2 → 2-3-4 tree (1-3 keys, 2-4 children) — good for learning
    - t=100 → typical for databases (199 keys per node)
    - t=500+ → typical for filesystem metadata
    
    Tree height with t=100 and 1 billion keys: ~5 levels.
    Each level = 1 disk read, so 5 reads to find anything.
    """

    def __init__(self, t=2):
        self.root = BTreeNode()
        self.t = t  # Minimum degree

    def search(self, key, node=None):
        """Search for key in the B-Tree. Returns (node, index) or None.
        
        At each node, we binary search within the keys (O(log t) per node),
        then follow the appropriate child pointer. Total: O(t·log_t(n))
        which simplifies to O(log n).
        """
        if node is None:
            node = self.root

        # Find the first key >= target (could use bisect for O(log t))
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1

        # Found the key in this node
        if i < len(node.keys) and key == node.keys[i]:
            return (node, i)

        # Hit a leaf without finding the key
        if node.leaf:
            return None

        # Recurse into the appropriate child
        return self.search(key, node.children[i])

    def insert(self, key):
        """Insert a key into the B-Tree.
        
        Strategy: proactively split full nodes on the way DOWN.
        This ensures we never need to split on the way back up,
        simplifying the code significantly.
        """
        root = self.root

        # Special case: if root is full, split it first
        # This is the ONLY way the tree grows taller
        if len(root.keys) == 2 * self.t - 1:
            new_root = BTreeNode(leaf=False)
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root

        self._insert_non_full(self.root, key)

    def _insert_non_full(self, node, key):
        """Insert key into a node that is guaranteed to have room.
        
        If the node is a leaf, insert directly.
        If internal, find the right child and recurse.
        Split any full child BEFORE descending into it.
        """
        i = len(node.keys) - 1

        if node.leaf:
            # Insert key in sorted position within this leaf
            node.keys.append(None)  # Extend by one
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]  # Shift right
                i -= 1
            node.keys[i + 1] = key
        else:
            # Find the child that should receive this key
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1

            # Proactive split: if that child is full, split BEFORE descending
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                # After split, the median moved up. Check which child to use.
                if key > node.keys[i]:
                    i += 1

            self._insert_non_full(node.children[i], key)

    def _split_child(self, parent, i):
        """Split the i-th child of parent (which must be full).
        
        The full child has 2t-1 keys. After split:
        - Median key moves up to parent at position i
        - Left half stays as original child (t-1 keys)
        - Right half becomes new child at position i+1 (t-1 keys)
        """
        t = self.t
        full_child = parent.children[i]
        new_node = BTreeNode(leaf=full_child.leaf)

        # Median key goes up to parent
        parent.keys.insert(i, full_child.keys[t - 1])
        parent.children.insert(i + 1, new_node)

        # Right half of keys goes to new node
        new_node.keys = full_child.keys[t:]
        full_child.keys = full_child.keys[:t - 1]  # Left half stays

        # If not a leaf, split children too
        if not full_child.leaf:
            new_node.children = full_child.children[t:]
            full_child.children = full_child.children[:t]

    def traverse(self, node=None):
        """In-order traversal — returns all keys in sorted order."""
        if node is None:
            node = self.root
        result = []
        for i in range(len(node.keys)):
            if not node.leaf:
                result.extend(self.traverse(node.children[i]))
            result.append(node.keys[i])
        if not node.leaf:
            result.extend(self.traverse(node.children[-1]))
        return result

    def height(self, node=None):
        """Height of the tree (0 for a single-node tree)."""
        if node is None:
            node = self.root
        if node.leaf:
            return 0
        return 1 + self.height(node.children[0])


# Usage
bt = BTree(t=2)  # 2-3-4 tree (1-3 keys per node)
for val in [10, 20, 5, 6, 12, 30, 7, 17]:
    bt.insert(val)

print("Sorted:", bt.traverse())     # [5, 6, 7, 10, 12, 17, 20, 30]
print("Height:", bt.height())        # Depends on splits
print("Search 12:", bt.search(12))   # (node, index) tuple
print("Search 15:", bt.search(15))   # None

class BTreeNode {
  constructor(leaf = true) {
    this.keys = [];       // Sorted keys (at most 2t-1)
    this.children = [];   // Child pointers (at most 2t for internal nodes)
    this.leaf = leaf;     // True if this node has no children
  }
}

class BTree {
  /**
   * B-Tree of minimum degree t.
   * - Each non-root node holds at least t-1 keys, at most 2t-1 keys.
   * - Each internal non-root node has at least t children, at most 2t children.
   * - The root may have as few as 1 key (or 0 if the tree is empty).
   * 
   * Common values:
   *   t=2 → 2-3-4 tree (learning)
   *   t=100 → databases
   *   t=500+ → filesystems
   */
  constructor(t = 2) {
    this.root = new BTreeNode();
    this.t = t;
  }

  search(node, key) {
    // Binary search within this node's sorted keys
    let lo = 0, hi = node.keys.length - 1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (node.keys[mid] === key) return { node, index: mid };
      if (node.keys[mid] < key) lo = mid + 1;
      else hi = mid - 1;
    }
    // lo = index of the child to follow (between keys[lo-1] and keys[lo])
    if (node.leaf) return null;
    return this.search(node.children[lo], key);
  }

  insert(key) {
    const root = this.root;

    // If the root is full, split it BEFORE inserting.
    // This is the ONLY way the tree grows taller.
    if (root.keys.length === 2 * this.t - 1) {
      const newRoot = new BTreeNode(false);
      newRoot.children.push(this.root);
      this._splitChild(newRoot, 0);
      this.root = newRoot;
    }

    this._insertNonFull(this.root, key);
  }

  _insertNonFull(node, key) {
    let i = node.keys.length - 1;

    if (node.leaf) {
      // Insert in sorted order within this leaf
      node.keys.push(null); // Make room
      while (i >= 0 && key < node.keys[i]) {
        node.keys[i + 1] = node.keys[i]; // Shift right
        i--;
      }
      node.keys[i + 1] = key;
    } else {
      // Find the correct child to descend into
      while (i >= 0 && key < node.keys[i]) i--;
      i++;

      // Proactive split: if that child is full, split BEFORE descending
      if (node.children[i].keys.length === 2 * this.t - 1) {
        this._splitChild(node, i);
        // After split, median moved up. Decide which half to descend into.
        if (key > node.keys[i]) i++;
      }

      this._insertNonFull(node.children[i], key);
    }
  }

  _splitChild(parent, i) {
    const t = this.t;
    const fullChild = parent.children[i];
    const newNode = new BTreeNode(fullChild.leaf);

    // Median key goes up to parent
    parent.keys.splice(i, 0, fullChild.keys[t - 1]);
    parent.children.splice(i + 1, 0, newNode);

    // Right half of keys → new node, left half stays
    newNode.keys = fullChild.keys.splice(t);     // keys from index t onward
    fullChild.keys.pop();                          // remove the median (already promoted)

    // If not a leaf, split children too
    if (!fullChild.leaf) {
      newNode.children = fullChild.children.splice(t);
    }
  }

  // In-order traversal → sorted keys
  traverse(node = this.root) {
    const result = [];
    for (let i = 0; i < node.keys.length; i++) {
      if (!node.leaf) result.push(...this.traverse(node.children[i]));
      result.push(node.keys[i]);
    }
    if (!node.leaf) result.push(...this.traverse(node.children[node.keys.length]));
    return result;
  }

  height(node = this.root) {
    if (node.leaf) return 0;
    return 1 + this.height(node.children[0]);
  }
}

// Usage
const bt = new BTree(2); // 2-3-4 tree
for (const val of [10, 20, 5, 6, 12, 30, 7, 17]) {
  bt.insert(val);
}
console.log("Sorted:", bt.traverse());    // [5, 6, 7, 10, 12, 17, 20, 30]
console.log("Height:", bt.height());
console.log("Search 12:", bt.search(bt.root, 12)); // { node, index }
console.log("Search 15:", bt.search(bt.root, 15)); // null

class BTreeWithDelete(BTree):
    """Extends BTree with full deletion support.
    
    Deletion cases:
    1. Key is in a leaf with > t-1 keys → just remove it
    2. Key is in an internal node → replace with predecessor/successor
    3. Key is in a leaf at minimum occupancy → borrow or merge first
    
    The implementation uses a "proactive fix" approach: ensure every
    node we descend into has at least t keys (one more than minimum),
    so deletion from a leaf never causes underflow.
    """

    def delete(self, key):
        """Delete a key from the B-Tree."""
        if not self.root.keys:
            return  # Empty tree

        self._delete(self.root, key)

        # If root has no keys but has a child, shrink the tree
        # This is the ONLY way the tree gets shorter
        if not self.root.keys and not self.root.leaf:
            self.root = self.root.children[0]

    def _delete(self, node, key):
        t = self.t
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1

        if node.leaf:
            # Case 1: Key is in this leaf — remove directly
            if i < len(node.keys) and node.keys[i] == key:
                node.keys.pop(i)
            return

        if i < len(node.keys) and node.keys[i] == key:
            # Case 2: Key is in this internal node
            self._delete_internal(node, i)
        else:
            # Case 3: Key is in a subtree — ensure child has enough keys
            if len(node.children[i].keys) < t:
                self._fix_child(node, i)
                # After fix, recalculate position (merge may have changed it)
                if i > len(node.keys):
                    i -= 1
                # Recheck if key moved to current node after merge
                if i < len(node.keys) and node.keys[i] == key:
                    self._delete_internal(node, i)
                    return
            self._delete(node.children[i], key)

    def _delete_internal(self, node, i):
        """Delete node.keys[i] from an internal node.
        Replace with predecessor or successor from a child."""
        t = self.t

        if len(node.children[i].keys) >= t:
            # Use in-order predecessor (rightmost key in left subtree)
            pred = self._get_predecessor(node.children[i])
            node.keys[i] = pred
            self._delete(node.children[i], pred)
        elif len(node.children[i + 1].keys) >= t:
            # Use in-order successor (leftmost key in right subtree)
            succ = self._get_successor(node.children[i + 1])
            node.keys[i] = succ
            self._delete(node.children[i + 1], succ)
        else:
            # Both children at minimum — merge them
            self._merge(node, i)
            self._delete(node.children[i], node.keys[i] if i < len(node.keys) else node.children[i].keys[t - 1])

    def _get_predecessor(self, node):
        """Get the largest key in this subtree."""
        while not node.leaf:
            node = node.children[-1]
        return node.keys[-1]

    def _get_successor(self, node):
        """Get the smallest key in this subtree."""
        while not node.leaf:
            node = node.children[0]
        return node.keys[0]

    def _fix_child(self, parent, i):
        """Ensure parent.children[i] has at least t keys.
        Try borrowing from a sibling first, then merge."""
        t = self.t

        if i > 0 and len(parent.children[i - 1].keys) >= t:
            # Borrow from left sibling (rotate right)
            child = parent.children[i]
            left = parent.children[i - 1]
            child.keys.insert(0, parent.keys[i - 1])
            parent.keys[i - 1] = left.keys.pop()
            if not left.leaf:
                child.children.insert(0, left.children.pop())

        elif i < len(parent.children) - 1 and len(parent.children[i + 1].keys) >= t:
            # Borrow from right sibling (rotate left)
            child = parent.children[i]
            right = parent.children[i + 1]
            child.keys.append(parent.keys[i])
            parent.keys[i] = right.keys.pop(0)
            if not right.leaf:
                child.children.append(right.children.pop(0))

        else:
            # Neither sibling can spare a key — merge
            if i < len(parent.children) - 1:
                self._merge(parent, i)
            else:
                self._merge(parent, i - 1)

    def _merge(self, parent, i):
        """Merge parent.children[i] and parent.children[i+1].
        Pulls parent.keys[i] down into the merged node."""
        t = self.t
        left = parent.children[i]
        right = parent.children[i + 1]

        # Pull the separating key down from parent
        left.keys.append(parent.keys.pop(i))

        # Move all keys and children from right to left
        left.keys.extend(right.keys)
        left.children.extend(right.children)

        # Remove the right child from parent
        parent.children.pop(i + 1)


# Usage
bt = BTreeWithDelete(t=2)
for val in [10, 20, 5, 6, 12, 30, 7, 17, 3, 8]:
    bt.insert(val)
print("Before:", bt.traverse())  # [3, 5, 6, 7, 8, 10, 12, 17, 20, 30]

bt.delete(6)
bt.delete(20)
bt.delete(10)
print("After:", bt.traverse())   # [3, 5, 7, 8, 12, 17, 30]

class SimpleDBIndex:
    """Simulates a database B+ Tree index for a single column.
    
    Real database indexes (PostgreSQL, MySQL/InnoDB, SQLite) work on
    the same principle: maintain a B+ Tree on the indexed column,
    where leaf nodes store (column_value → row_id) mappings.
    
    Without an index: SELECT WHERE age=25 scans ALL rows (O(n)).
    With an index: follows the tree to the exact leaf (O(log n)).
    """

    def __init__(self, column_name):
        self.column_name = column_name
        self.btree = BTree(t=3)  # Small t for demonstration
        self.value_to_rows = {}  # value → set of row IDs

    def index_row(self, value, row_id):
        """Add a row to the index. Called on INSERT or when creating the index."""
        if value not in self.value_to_rows:
            self.btree.insert(value)
            self.value_to_rows[value] = set()
        self.value_to_rows[value].add(row_id)

    def lookup_exact(self, value):
        """Find all rows where column = value. O(log n).
        
        This is what happens when you run:
        SELECT * FROM users WHERE age = 25
        """
        result = self.btree.search(value)
        if result is None:
            return set()
        return self.value_to_rows.get(value, set())

    def lookup_range(self, min_val, max_val):
        """Find all rows where min_val <= column <= max_val.
        
        This is what happens when you run:
        SELECT * FROM users WHERE age BETWEEN 25 AND 35
        
        In a real B+ Tree, this walks the leaf linked list.
        Here we simulate it with the in-order traversal.
        """
        all_keys = self.btree.traverse()
        result = set()
        for key in all_keys:
            if min_val <= key <= max_val:
                result.update(self.value_to_rows.get(key, set()))
            elif key > max_val:
                break  # Keys are sorted, so we can stop early
        return result


class SimpleDatabase:
    """Toy database demonstrating index vs. full scan performance."""

    def __init__(self):
        self.rows = []      # List of row dicts
        self.indexes = {}   # column_name → SimpleDBIndex

    def insert(self, row):
        row_id = len(self.rows)
        self.rows.append(row)
        # Update all indexes
        for col, index in self.indexes.items():
            if col in row:
                index.index_row(row[col], row_id)
        return row_id

    def create_index(self, column):
        """CREATE INDEX on a column. Indexes all existing rows."""
        index = SimpleDBIndex(column)
        for row_id, row in enumerate(self.rows):
            if column in row:
                index.index_row(row[column], row_id)
        self.indexes[column] = index
        return f"Index created on '{column}' ({len(self.rows)} rows indexed)"

    def query(self, column, value):
        """SELECT * FROM table WHERE column = value."""
        if column in self.indexes:
            # INDEX SCAN: O(log n) via B-Tree
            row_ids = self.indexes[column].lookup_exact(value)
            return [self.rows[rid] for rid in row_ids]
        else:
            # FULL TABLE SCAN: O(n) — checks every row
            return [row for row in self.rows if row.get(column) == value]

    def query_range(self, column, min_val, max_val):
        """SELECT * FROM table WHERE column BETWEEN min AND max."""
        if column in self.indexes:
            row_ids = self.indexes[column].lookup_range(min_val, max_val)
            return [self.rows[rid] for rid in row_ids]
        else:
            return [row for row in self.rows
                    if min_val <= row.get(column, float('inf')) <= max_val]


# Demo
db = SimpleDatabase()

# Insert some users
users = [
    {"name": "Alice", "age": 30, "dept": "Engineering"},
    {"name": "Bob", "age": 25, "dept": "Marketing"},
    {"name": "Charlie", "age": 35, "dept": "Engineering"},
    {"name": "Dave", "age": 28, "dept": "Sales"},
    {"name": "Eve", "age": 30, "dept": "Engineering"},
    {"name": "Frank", "age": 22, "dept": "Marketing"},
]
for user in users:
    db.insert(user)

# Without index: full scan
print("Without index (full scan):")
results = db.query("age", 30)
print(f"  Age=30: {[r['name'] for r in results]}")  # ['Alice', 'Eve']

# Create index on 'age'
print(db.create_index("age"))

# With index: B-Tree lookup
print("\nWith index (B-Tree lookup):")
results = db.query("age", 30)
print(f"  Age=30: {[r['name'] for r in results]}")  # ['Alice', 'Eve']

# Range query
results = db.query_range("age", 25, 30)
print(f"  Age 25-30: {[r['name'] for r in results]}")  # ['Bob', 'Dave', 'Alice', 'Eve']