B-Tree ও B+ Tree — disk-এর জন্য জন্ম নেওয়া tree

import math
import random


class BTNode:
    __slots__ = ('keys', 'children', 'leaf')

    def __init__(self, leaf=True):
        self.keys = []          # sorted
        self.children = []      # leaf হলে খালি
        self.leaf = leaf


class BTree:
    def __init__(self, t):
        assert t >= 2, 'minimum degree অন্তত ২'
        self.t = t
        self.root = BTNode(True)
        self.splits = 0

    def _split_child(self, x, i):
        """x-এর i-তম (full) child দুই-ভাগ; median x-এ ওঠে"""
        self.splits += 1
        t = self.t
        y = x.children[i]
        z = BTNode(y.leaf)
        mid = y.keys[t - 1]
        z.keys = y.keys[t:]             # উপরের t−1 key z-এ
        y.keys = y.keys[:t - 1]         # নিচের t−1 y-তে
        if not y.leaf:
            z.children = y.children[t:]
            y.children = y.children[:t]
        x.children.insert(i + 1, z)
        x.keys.insert(i, mid)

    def _insert_nonfull(self, x, key):
        while not x.leaf:
            i = len(x.keys) - 1
            while i >= 0 and key \< x.keys[i]:
                i -= 1
            i += 1
            if len(x.children[i].keys) == 2 * self.t - 1:
                self._split_child(x, i)      # preemptive!
                if key > x.keys[i]:
                    i += 1
            x = x.children[i]
        pos = len(x.keys)
        while pos > 0 and x.keys[pos - 1] > key:
            pos -= 1
        x.keys.insert(pos, key)

    def insert(self, key):
        r = self.root
        if len(r.keys) == 2 * self.t - 1:
            s = BTNode(False)                # নতুন root —
            s.children = [r]                 # height বাড়ে শুধু এখানে
            self.root = s
            self._split_child(s, 0)
            self._insert_nonfull(s, key)
        else:
            self._insert_nonfull(r, key)

    def in_order(self, x=None):
        x = x if x is not None else self.root
        if x.leaf:
            yield from x.keys
        else:
            for i, k in enumerate(x.keys):
                yield from self.in_order(x.children[i])
                yield k
            yield from self.in_order(x.children[-1])

    def height(self):
        n, h = self.root, 1
        while not n.leaf:
            n = n.children[0]; h += 1
        return h

    def validate(self, x=None, is_root=True):
        """সব property assert; returns leaf-depth"""
        x = x if x is not None else self.root
        assert len(x.keys) \<= 2 * self.t - 1, 'over-full node!'
        if not is_root:
            assert len(x.keys) >= self.t - 1, 'under-full node!'
        assert all(x.keys[i] \< x.keys[i + 1]
                   for i in range(len(x.keys) - 1)), 'unsorted node!'
        if x.leaf:
            return 0
        assert len(x.children) == len(x.keys) + 1, 'child count!'
        depths = {self.validate(c, False) for c in x.children}
        assert len(depths) == 1, 'leaf-depth সমান নয়!'
        return 1 + depths.pop()


if __name__ == '__main__':
    bt = BTree(3)
    before = marks = 0
    events = []
    for k in range(1, 13):
        pre = bt.splits
        bt.insert(k)
        bt.validate()
        if bt.splits > pre:
            events.append((k, bt.splits))
    print('splits:', events)
    print('height:', bt.height())
    assert list(bt.in_order()) == list(range(1, 13))
    print('in-order OK:', list(bt.in_order()))

    for trial in range(20):                  # assertion suite
        tr = BTree(random.choice([2, 3, 4]))
        ks = random.sample(range(100_000), 500)
        for k in ks:
            tr.insert(k); tr.validate()
        assert list(tr.in_order()) == sorted(ks)
        seq = BTree(tr.t)                     # sorted attack — harmless
        for k in range(1, 301):
            seq.insert(k); seq.validate()
        assert list(seq.in_order()) == list(range(1, 301))
    print('assertion suite OK — ২০ trial × (random + sorted)')

প্রত্যাশিত output:

splits: [(6, 1), (9, 2), (12, 3)]
height: 2
in-order OK: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
assertion suite OK — ২০ trial × (random + sorted)

(example-এর hand-trace-এর সাথে splits মিলল? মিললে split-mechanics আয়ত্তে।)

নিজে বাড়ান: (১) search(key) + node-visit counter — height-এর সাথে মিলান; (২) delete() — underflow-এ borrow/merge; validator বলবে কোথায় ভুল; (৩) fill-factor মাপুন (bytes_used tracking) — random insert- এ বিখ্যাত ~৬৯% আসে, bulk-load-এ ১০০% কেন engines সেট করে তার উত্তর।