B+ Tree Implementation

কেন এই প্রজেক্ট

B+ tree-এর সব বইয়ের picture একই: গাছ, leaf-এ data, internal-এ navigation। Picture যা দেখায় না সেটাই আসল কাজ — separator key-গুলো আসলে কার মালিকানায়? Sibling থেকে borrow করলে parent-এর separator কে বদলাবে? Merge হলে কোনটা মুছবে? এই ছোট ছোট bookkeeping-ই B+ tree-এর সব bug-এর ঘর, আর paper-এ implement না করলে কখনো ধরাই পড়ে না।

দ্বিতীয় কারণটা discipline: আমরা pointer-এ গাছ বানাবো না — fixed-size bytearray-এ, ঠিক যেন প্রতিটা node একটা disk page। সেই নিয়ম মানলেই serialization প্রশ্নই ওঠে না, আর cache-oblivious access pattern চোখে পড়ে। শেষে oracle dict-এর বিরুদ্ধে লাখ অপের stress test — random workload-এ যে bug পালায় না।

ধাপে ধাপে

১. Page abstraction — ডিস্ক simulation

PAGE_SIZE = 4096

class Disk:
    def __init__(self):
        self.pages: list[bytearray] = []

    def alloc(self) -> int:
        self.pages.append(bytearray(PAGE_SIZE))
        return len(self.pages) - 1           # page id

    def read(self, pid: int) -> memoryview:
        return memoryview(self.pages[pid])

    def write(self, pid: int, buf: bytes):
        self.pages[pid][:] = buf

নিয়ম: node-এর সব state এই PAGE_SIZE-এর ভেতরে থাকতে হবে। কোনো Python object field নয় — pack/unpack করেই পড়ুন-লিখুন। এই constraint-ই পরের সব ধাপকে সৎ রাখে।

Leaf slot: (key:int, value:int); internal slot: (sep_key:int, child_pid):

import struct

HDR = struct.Struct("<BHHI")       # kind | nslots | free_off | next_leaf

class Node:
    def __init__(self, disk, pid, kind):
        self.disk, self.pid, self.kind = disk, pid, kind
        raw = disk.read(pid)
        self.kind, self.n, self.free_off, self.next = HDR.unpack_from(raw)

    @classmethod
    def new(cls, disk, kind):
        pid = disk.alloc()
        buf = bytearray(PAGE_SIZE)
        HDR.pack_into(buf, 0, kind, 0, HDR.size, 0)
        disk.write(pid, buf)
        return cls(disk, pid, kind)

Slot গুলো পেজের শেষ প্রান্ত থেকে সামনের দিকে বাড়ুক — এই slotted arrangement মাঝে জায়গা variable-size key-এর দিনে কাজে লাগবে।

৩. Insert with proactive split

নিচে নামার সময়েই full child ভাগ করুন — পরে উপরে ফিরে fix করার recursion বাঁচে:

MAX_SLOTS = (PAGE_SIZE - HDR.size) // 12      # (key, value) = 12 bytes
MIN_SLOTS = MAX_SLOTS // 2

def insert(self, key, val):
    if self.root.full():
        new_root = Node.new(self.disk, INTERNAL)
        new_root.append_child(self.root.pid)
        new_root.split_child(0)
        self.root = new_root
    self._insert_nonfull(self.root, key, val)

def _insert_nonfull(self, node, key, val):
    if node.kind == LEAF:
        node.put(key, val); return
    i = node.rank(key)                        # sep <= key হলে ডানে?
    child = self.load(node.child_at(i))
    if child.will_overflow():
        node.split_child(i)                   # proactive!
        i = node.rank(key)                    # separator বদলালো — rank আবার
    self._insert_nonfull(self.load(node.child_at(i)), key, val)

Split-এর মাঝ-বিন্দু (median) উপরে ওঠে। Proactive পদ্ধতিতে root ছাড়া কোনো node কখনো overflow-ই করে না — এটাই পুরো design-এর লাভ।

Checkpoint: ছোট order (MAX_SLOTS = 4)-এ হাতে ১..১০ insert করে print করুন — প্রতিটা split-এর পরে গাছের shape বইয়ের figure-এর সঙ্গে মিলবে।

৪. Delete — borrow আর merge

Underflow (n < MIN_SLOTS) সামলানোর তিন রাস্তা, এই ক্রমে চেষ্টা করুন:

def fix_underflow(self, parent, i):
    child = self.load(parent.child_at(i))
    if child.n >= MIN_SLOTS:
        return                                 # কিছুই করা লাগে না
    left  = self.try_load(parent.child_at(i - 1)) if i > 0 else None
    right = self.try_load(parent.child_at(i + 1))
    if left and left.n > MIN_SLOTS:
        child.borrow_from_left(left, parent, i)      # rotate through parent
    elif right and right.n > MIN_SLOTS:
        child.borrow_from_right(right, parent, i)
    elif left:
        parent.merge_children(i - 1)           # left + sep + child
    else:
        parent.merge_children(i)               # child + sep + right

Merge-এ parent থেকে এক separator মুছে যায় — parent নিজেই underflow-এ পড়তে পারে, তাই recursion উপরে ওঠে। Root-এর একমাত্র বিশেষ অধিকার: সে MIN মানে না, খালি হলে তার একমাত্র child নতুন root।

৫. Separator maintenance — সব bug-এর উৎস

Borrow/merge-এর পরে parent-এর separator অবশ্যই right subtree-র সবচেয়ে ছোট key-এর সমান থাকতে হবে:

def borrow_from_left(self, left, parent, i):
    my_first = self.key_at(0)
    moved = left.pop_max()                     # leaf: (key,val); internal: (key,child)
    self.prepend(moved)
    parent.set_sep(i - 1, self.key_at(0))      # ← এই লাইনটাই ভোলা হয়

ভুলের চেহারা চেনুন: delete-এর পরে কোনো key search-এ পাওয়া যায় না যদিও leaf-এ আছে — separator পুরনো মানে আটকে থাকায় navigation ভুল দিকে যায়। Validator (ধাপ ৮) এই ভাঙন ধরে ফেলে, তাই ভয় নেই।

৬. Leaf-chain range iterator

def range_scan(self, lo, hi):
    leaf = self.find_leaf(lo)
    while leaf is not None:
        for key, val in leaf.items():
            if key > hi:
                return
            if key >= lo:
                yield key, val
        leaf = self.load(leaf.next) if leaf.next else None

Point lookup-এর চেয়ে এটাই B+-কে B থেকে আলাদা করে: উপরে উঠার দরকার নেই, leaf chain-এ শুধু সামনে হাঁটুন। Sequential page access — ডিস্কের ভাষায় এটাই মূল্যবান।

৭. Persistence — serialize/deserialize

Pages যেহেতু bytearray, পুরো tree মানে পেজের বাঁধা ক্রম:

def save(self, path):
    with open(path, "wb") as f:
        f.write(struct.pack("<III", MAGIC, VERSION, self.root_pid))
        f.write(struct.pack("<I", len(self.disk.pages)))
        for page in self.disk.pages:
            f.write(page)

def load_tree(path) -> "BPlusTree":
    # header পড়ে pages একটার পর একটা bytearray-এ বসান — ব্যস, গাছ ফিরে পেলেন

Round-trip যাচাই: save → load → একই ১০০ query-র উত্তর হুবহু এক, আর root_pid-ও এক। Byte-exact না মিললে layout-এ endianness বা padding ফাঁদ আছে।

৮. Stress test + invariant validator

প্রতি operation-এর পরে validator — ধীর, কিন্তু bug যেদিন ধরবে সেদিন বুঝবেন দাম কত কম:

def validate(tree):
    depths = set()
    def walk(pid, depth, lo, hi):
        node = tree.load(pid)
        keys = node.keys()
        assert keys == sorted(keys), f"{pid}: unsorted"
        assert lo <= (keys[0] if keys else lo) and (not keys or keys[-1] < hi) or True
        assert MIN_SLOTS <= node.n or node.pid == tree.root_pid
        if node.kind == LEAF:
            depths.add(depth)
            return keys[0] if keys else None
        for i in range(node.n):
            walk(node.child_at(i), depth + 1, ...)
        # separator == right subtree-র min — প্রতিটা edge-এ যাচাই
    walk(tree.root_pid, 0, float("-inf"), float("inf"))
    assert len(depths) == 1, "leaf-দের depth ভিন্ন!"

oracle = {}
tree = BPlusTree(order=MAX_SLOTS)
for step in range(100_000):
    k = random.randrange(50_000)
    if random.random() < 0.6:
        tree.insert(k, random.randrange(2**31)); oracle[k] = tree.last_val
    else:
        tree.delete(k); oracle.pop(k, None)
    validate(tree)                            # প্রতি op-এ — slow but sure
    if step % 1_000 == 0:
        assert tree.range_scan_all() == sorted(oracle.items())

শেষে stats report বের করুন: tree depth, স্তরভেদে node count, occupancy histogram। Random workload-এ গড় fill factor প্রায় ৬৯%-এ থিমে — এই সংখ্যাটা নিজে দেখলে textbook-এর “2/3 full” কথাটা আর মুখস্থ থাকে না।

নিজেকে চ্যালেঞ্জ করুন

Variable-size string key — slotted page-এর free_off এখন সত্যিই দরকার
Bulk-load — sorted input থেকে নিচ থেকে গাছ বানানো, split-এর খরচ শূন্যে
Cursor invalidation — iteration-এর মাঝে delete এলে leaf-chain fix
Copy-on-write snapshot — clone-on-modify page, দুই reader দুই version
LRU page cache Disk-এর উপরে — hot tree কত page-এ আঁটে মাপুন
Prefix compression — internal separator-এ common prefix share, fanout gain মাপুন

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানে	পরে
Page-id indirection	Buffer pool project — একই Disk interface-এ eviction বসবে
Invariant validator habit	Level 9 — distributed structure-এ assertion ছাড়া debug অসম্ভব
Oracle-diff stress testing	যেকোনো optimizer/refactor-এর safety net
Occupancy/space accounting	Storage tuning — fill factor আসলে money
Leaf-chain scan	Level 8 Mini SQL Engine — index scan operator হুবহু এটা

মাইলস্টোন

আগে যা পড়া দরকার