B-tree আর B+ tree — ডিস্ক আর ডেটাবেসের tree

১ · ডিস্কে binary tree কেন ধীর — memory hierarchy আর block

পর্ব ২৭–২৯-এ আপনি binary search tree আর তাকে ভারসাম্যে রাখার উপায় দেখেছেন: n টি key-তে উচ্চতা প্রায় log₂ n, তাই খোঁজা O(log n). দশ লাখ key-তে মাত্র ২০টির মতো ধাপ। তাহলে সমস্যা কোথায়? সমস্যা হলো, এই হিসাব ধরে নেয় যে প্রতিটি node দেখতে সমান সময় লাগে — অর্থাৎ পুরো tree RAM-এ আছে। কিন্তু একটি ব্যাংকের লেনদেনের টেবিলে শত কোটি row থাকতে পারে, যা RAM-এ ধরে না। ডেটা থাকে SSD বা hard disk-এ, আর তখন খেলার নিয়ম পুরো বদলে যায়।

কম্পিউটারের স্টোরেজও এমন স্তরে সাজানো, যাকে বলে memory hierarchy (বিস্তারিত দেখুন কম্পিউটারের মৌলিক ধারণা কোর্সের মেমরি হায়ারার্কির পর্বে). ওপরের স্তর দ্রুত কিন্তু ছোট আর দামি, নিচের স্তর ধীর কিন্তু বিশাল আর সস্তা। নিচের সংখ্যাগুলো মোটামুটি মাপ — যন্ত্রভেদে কম-বেশি হয়, কিন্তু অনুপাতটাই আসল কথা:

Hard disk-এর এত দেরি কেন? ভেতরে একটি চাকতি ঘোরে, আর একটি যান্ত্রিক হাত (head) সঠিক track-এ সরে গিয়ে অপেক্ষা করে কখন দরকারি অংশটি তার নিচে ঘুরে আসবে। এই নড়াচড়াই মিলিসেকেন্ড খায়। কিন্তু একবার পৌঁছে গেলে পাশাপাশি অনেক byte পড়া প্রায় বিনা খরচে হয়। SSD-তে নড়াচড়ার অংশ নেই, তবু সে ডেটা দেয় পুরো page ধরে। তাই ডিস্ক বা SSD থেকে কখনো একটি byte আসে না — আসে একটি পুরো disk block বা page, সাধারণত কয়েক KB. এক byte লাগলেও খরচ পুরো block-এর, আর block-এর বাকি byte-গুলো তখন প্রায় বিনা মূল্যে পাওয়া। এই অপেক্ষার সময়কে বলে latency.

এবার হিসাব করুন। একশো কোটি (10⁹) key-এর একটি পুরো ভারসাম্যপূর্ণ binary tree-র উচ্চতা প্রায় log₂ 10⁹ ≈ ৩০। প্রতিটি node ডিস্কের কোনো এলোমেলো জায়গায় — তাই একটি খোঁজায় ৩০টি এলোমেলো disk read, hard disk-এ প্রায় ৩০ × ১০ ms = ০.৩ সেকেন্ড। একটি ওয়েবসাইটে প্রতি সেকেন্ডে হাজার জন খুঁজলে এটি অচল। আর সবচেয়ে বড় অপচয়টি দেখুন: প্রতিটি read-এ ৪ KB-র block আনা হলো, অথচ কাজে লাগল শুধু একটি key আর দুটি pointer — হয়তো ২০ byte. বাকি ৯৯% ফেলে দেওয়া।

External-memory model — block গুনে বিশ্লেষণ

এই বাস্তবতা ধরতে ১৯৮৮ সালে Alok Aggarwal আর Jeffrey Vitter একটি বিশ্লেষণ পদ্ধতি দাঁড় করান, যাকে বলে external-memory model বা I/O model. পর্ব ০২-এর RAM model-এ প্রতিটি সরল ধাপের খরচ ১ ধরা হতো। এখানে ছবিটা অন্য রকম:

• একটি দ্রুত মেমরি, যার মাপ M, আর একটি অসীম বড় কিন্তু ধীর ডিস্ক।
• ডিস্ক থেকে ডেটা আসে-যায় শুধু B মাপের block ধরে (B = একটি block-এ কয়টি key ধরে)।
• খরচ = কয়টি block আনা-নেওয়া (I/O) হলো. মেমরির ভেতরের CPU-র কাজ বিনা খরচে ধরা হয়, কারণ সেটি তুলনায় নগণ্য।

এই মডেলে কয়েকটি পরিচিত কাজের খরচ: N টি key একবার পড়ে যাওয়া (scan) Θ(N/B) I/O — প্রতিটি block একবার। ডিস্কে রাখা সাজানো অ্যারেতে binary search প্রায় log₂(N/B) I/O — শেষের দিকে খোঁজা একটি block-এর ভেতরে চলে আসে, তার আগে প্রতিটি ধাপ নতুন block. Binary search tree-তে log₂ N I/O. আর এই পর্বের B-tree-তে মাত্র Θ(log_B N) I/O. B = ১০০০ হলে log₁₀₀₀ 10⁹ = ৩ — ৩০ নয়, ৩! ভিত্তি ২ থেকে ১০০০-এ গেলে log-এর মান প্রায় দশ ভাগের এক ভাগ হয়ে যায় (log₂ 1000 ≈ ১০)। পর্ব ২১-এর external sorting-ও এই মডেলেরই বিষয়।

২ · B-tree-র সংজ্ঞা — minimum degree t আর উচ্চতার সীমা

B-tree একটি search tree, যার প্রতিটি node-এ একাধিক সাজানো key থাকে। k টি key-ওয়ালা একটি internal node-এর ঠিক k + 1 টি সন্তান, আর key-গুলোই সন্তানদের মাঝে সীমারেখা টানে — এদের বলে separator key. যেমন node [20 50]-এর তিন সন্তান: প্রথমটিতে সব key 20-এর ছোট, দ্বিতীয়টিতে 20 থেকে 50-এর মাঝে, তৃতীয়টিতে 50-এর বড়। পর্ব ২৭-এর BST-র “বাঁয়ে ছোট, ডানে বড়” নিয়মই, শুধু দুই দিকের বদলে অনেক দিকে। লাইব্রেরির তাকের গায়ে লেখা থাকে “০০০–২৯৯ | ৩০০–৫৯৯ | ৬০০–৯৯৯” — সেই লেবেল দেখেই ঠিক করেন কোন তাকে যাবেন; separator key ঠিক সেই লেবেল।

Minimum degree t-এর একটি B-tree এই পাঁচটি নিয়ম মানে:

1. প্রতিটি node-এর key-গুলো ছোট থেকে বড় ক্রমে সাজানো: k₁ < k₂ < … < k_m.
2. m টি key-ওয়ালা internal node-এর m + 1 টি সন্তান; i-তম সন্তানের subtree-র সব key k_i−1 আর k_i-এর মাঝে।
3. সব leaf একই গভীরতায় — tree পুরোপুরি ভারসাম্যপূর্ণ, কোনো শাখা অন্যটির চেয়ে লম্বা নয়।
4. সর্বোচ্চ: প্রতিটি node-এ সর্বোচ্চ 2t − 1 টি key (তাই সর্বোচ্চ 2t টি সন্তান)। 2t − 1 টি key থাকলে node-টি “ভরা” (full).
5. সর্বনিম্ন: root ছাড়া প্রতিটি node-এ অন্তত t − 1 টি key (internal হলে অন্তত t টি সন্তান)। Tree খালি না হলে root-এ অন্তত ১টি key.

নিয়ম ৪ আর ৫ মিলে প্রতিটি node অন্তত প্রায় অর্ধেক ভরা থাকে — জায়গার অপচয় সীমিত। আর নিয়ম ৩ নিশ্চিত করে যে কোনো খোঁজা কখনো অপ্রত্যাশিত লম্বা পথ ধরবে না। বাস্তবে t অনেক বড়: একটি 16 KB-র page-এ প্রতিটি entry মোটামুটি ১৬ byte ধরলে প্রায় এক হাজার entry ধরে, অর্থাৎ t কয়েকশো। কাগজে-কলমে বোঝার জন্য আমরা ছোট t (২ বা ৩) নেব।

উচ্চতার সীমা — কেন log_t n

উপপাদ্য (CLRS): n ≥ 1 টি key-এর, minimum degree t-এর যেকোনো B-tree-র উচ্চতা h (root থেকে leaf পর্যন্ত edge-এর সংখ্যা) মানে

প্রমাণ. উচ্চতা h-এর একটি B-tree-তে সবচেয়ে কম কয়টি key থাকতে পারে, তা গুনি। Root-এ অন্তত ১টি key, তাই অন্তত ২টি সন্তান — গভীরতা ১-এ অন্তত ২টি node. এদের প্রত্যেকের অন্তত t টি সন্তান, তাই গভীরতা ২-এ অন্তত 2t টি node, গভীরতা ৩-এ অন্তত 2t² টি; সাধারণভাবে গভীরতা i-তে (1 ≤ i ≤ h) অন্তত 2tⁱ⁻¹ টি node, প্রত্যেকটিতে অন্তত t − 1 টি key. তাই

মাঝের ধাপে পর্ব ০৬-এর geometric series: 1 + t + … + t^h−1 = (t^h − 1)/(t − 1). তাহলে t^h ≤ (n + 1)/2, আর দুই দিকে log_t নিলেই উপপাদ্য। ∎ উল্টো দিকে, প্রতিটি node পুরো ভরা হলে (2t − 1 key, 2t সন্তান) উচ্চতা h-এ সর্বোচ্চ (2t)^h+1 − 1 টি key ধরে, তাই h ≥ log_2t(n + 1) − 1. অর্থাৎ উচ্চতা সবসময় Θ(log_t n).

সংখ্যায় দেখুন: t = ৫০০ আর n = 10⁹ হলে (n + 1)/2 ≈ 5 × 10⁸, আর log₅₀₀(5 × 10⁸) ≈ ৩.২২ — তাই h ≤ ৩, অর্থাৎ root থেকে leaf পর্যন্ত বড়জোর ৪টি node. একই n-এ binary tree-তে প্রায় ৩০টি। আর root ও তার ঠিক নিচের স্তর সাধারণত সবসময় RAM-এ থাকে (সেগুলো বারবার লাগে, আর মাপে ছোট) — তাই বাস্তবে একটি খোঁজায় মাত্র ১–২টি disk read.

৩ · Search — প্রতিটি node মানে একটি disk read

খোঁজা BST-র মতোই, শুধু প্রতিটি node-এ দুই দিকের বদলে অনেক দিকের সিদ্ধান্ত। Root থেকে শুরু করুন। Node-টি ডিস্ক থেকে পড়ুন (একটি I/O), তার key-গুলোর মধ্যে খুঁজুন x-এর জায়গা কোথায়। x পেয়ে গেলে শেষ। না পেলে, x যে দুটি key-এর মাঝে পড়ে, সেই ফাঁকের সন্তানে নামুন। Leaf-এ পৌঁছেও না পেলে, x tree-তে নেই।

Pseudocode — B-tree search (keys of a node are 0-based: v.key[0 .. v.n-1])

search(v, x):                                  // v has just been read from disk
    i = first index with v.key[i] >= x         // linear scan, or binary search inside the node
    if i < v.n and v.key[i] == x:  return (v, i)
    if v is a leaf:                return NOT_FOUND
    DISK-READ(v.child[i])                      // one I/O per level
    return search(v.child[i], x)

নিচে t = 3-এর একটি tree (প্রতিটি non-root node-এ ২ থেকে ৫টি key). এতে ২৪টি key, উচ্চতা ২। এখানে 66 খুঁজছি:

বিশ্লেষণ. প্রতিটি স্তরে একটি node, তাই disk read O(h) = O(log_t n). মেমরিতে CPU-র কাজ: প্রতিটি node-এ সর্বোচ্চ 2t − 1 টি key, সরলভাবে একে একে দেখলে O(t), node-এর ভেতরে binary search (পর্ব ১৮) করলে O(log t). মোট CPU সময় O(t log_t n), বা binary search দিয়ে O(log t · log_t n) = O(log n). লক্ষ করুন শেষের হিসাবটি: মোট তুলনা BST-র মতোই প্রায় log₂ n. B-tree তুলনা কমায় না — সে তুলনাগুলোকে কম কয়টি block-এ গুছিয়ে আনে। জায়গা: recursion না করে লুপে লিখলে বাড়তি O(1) node-এর জায়গা (মেমরিতে একটি block-এর বাফার)।

৪ · Insert — ভরা node ভাগ করা (node split)

নতুন key x সবসময় একটি leaf-এ ঢোকে — খোঁজার পথ ধরে নেমে যে leaf-এ x থাকার কথা, সেখানে সাজানো জায়গায়। কিন্তু leaf যদি ভরা থাকে (2t − 1 key)? তখন node split: ভরা node-এর মাঝের key (median, index t − 1) উঠে যায় parent-এ, বাঁয়ের t − 1 টি key থেকে যায় পুরোনো node-এ, আর ডানের t − 1 টি key যায় একটি নতুন node-এ। Parent-এ একটি key আর একটি সন্তান বাড়ে। মাঝের key-টি দুই নতুন node-এর মাঝে নিখুঁত separator, তাই search tree-র নিয়ম ঠিক থাকে।

ঝামেলা হলো, parent-ও যদি ভরা থাকে, তাহলে median ঢুকবে কোথায়? তাকেও ভাগ করতে হবে, তার parent-কেও হয়তো — ভাঙন ওপরের দিকে চেইনের মতো ছড়াতে পারে। দুটি সমাধান:

• নিচ থেকে ওপরে (bottom-up): আগে leaf-এ ঢোকান, উপচে পড়লে split করে median ওপরে পাঠান, দরকার হলে বারবার। এতে নামার পথ মনে রাখতে হয় (stack বা parent pointer).
• ওপর থেকে নিচে (proactive বা top-down splitting, CLRS): নামার পথে যে ভরা node-ই পান, ঢোকার আগেই সেটি ভাগ করে ফেলুন — আপনার এই key সেখানে যাক বা না যাক। তাহলে যখনই কোনো node ভাগ করবেন, তার parent নিশ্চিতভাবে ভরা নয় (তাকে আগের ধাপেই ভাগ করা হয়েছে), তাই median-এর জায়গা সবসময় আছে। এক যাত্রায় নিচে নামা, আর কখনো ওপরে ফিরতে হয় না।

Pseudocode — B-tree insert with proactive splitting (CLRS style, 0-based keys)

splitChild(p, i):                     // p is NOT full; y = p.child[i] has 2t-1 keys
    z = new node with y.key[t .. 2t-2]  and, if y is internal, y.child[t .. 2t-1]
    insert y.key[t-1] (the median) into p at position i
    p.child[i+1] = z
    y keeps only y.key[0 .. t-2]  (and y.child[0 .. t-1])
    DISK-WRITE(y);  DISK-WRITE(z);  DISK-WRITE(p)

insert(x):
    if root has 2t-1 keys:            // the ONLY way the tree gets taller
        s = new node with child[0] = root;  root = s;  splitChild(s, 0)
    v = root
    while v is not a leaf:
        i = number of keys in v that are <= x
        if v.child[i] has 2t-1 keys:
            splitChild(v, i)
            if x > v.key[i]:  i = i + 1   // x belongs to the new right half
        v = v.child[i]
    put x into leaf v at its sorted position;  DISK-WRITE(v)

এবার একটি খালি t = 2-এর tree-তে (প্রতিটি node-এ ১ থেকে ৩টি key) পরপর ঢোকাই 50, 20, 80, 10, 30, 60, 90, 40, 70, 25. প্রতিটি ধাপ নিচের প্রোগ্রামের আউটপুটের সাথে মেলে:

কেন সব leaf সবসময় একই গভীরতায় থাকে — invariant. একটি split একটি node-কে একই স্তরের দুটি node বানায়; কোনো leaf-এর গভীরতা বদলায় না। গভীরতা বদলায় একমাত্র root split-এ: তখন নতুন root সবার ওপরে বসে, আর প্রতিটি leaf-এর গভীরতা একসাথে ১ বাড়ে। BST নিচে leaf ঝুলিয়ে বাড়ে, তাই একদিকে লম্বা হয়ে যেতে পারে; B-tree বাড়ে মাথার দিক থেকে, তাই কখনো হেলে পড়ে না। আর key-সংখ্যার নিয়ম: split-এ 2t − 1 টি key থেকে দুটি node পায় ঠিক t − 1 টি করে — সর্বনিম্ন সীমার মধ্যে; parent-এ একটি key বাড়ে, কিন্তু proactive নিয়মে parent আগে থেকেই ভরা ছিল না, তাই সর্বোচ্চ সীমাও ঠিক থাকে। এটি পর্ব ০৩-এর loop invariant-এর মতো যুক্তি: “বর্তমান node v কখনো ভরা নয়” — শুরুতে root-এর বিশেষ split এটি সত্য করে, আর প্রতিটি নামার আগে সন্তানের split এটি সত্য রাখে।

খরচ. প্রতি স্তরে বড়জোর একটি split, আর প্রতিটি split-এ ৩টি node লেখা — তাই disk I/O O(h) = O(log_t n). CPU: প্রতিটি split-এ প্রায় t টি key সরানো, প্রতিটি node-এ সঠিক সন্তান খোঁজা O(t) — মোট O(t log_t n). বাড়তি মেমরি: একই সময়ে মাত্র কয়েকটি node, O(t).

#include <algorithm>
#include <deque>
#include <initializer_list>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int T = 2;                                   // minimum degree: every node holds 1..3 keys
struct Node { vector<int> k; vector<Node*> c; };   // keys, children (empty = leaf)
deque<Node> pool;                                  // owns all nodes; pointers stay valid
Node* root = &pool.emplace_back();
void split(Node* p, int i) {                       // p->c[i] is full (2T-1 keys)
    Node* y = p->c[i]; Node* z = &pool.emplace_back();
    z->k.assign(y->k.begin() + T, y->k.end());     // right half moves to a new node
    if (!y->c.empty()) { z->c.assign(y->c.begin() + T, y->c.end()); y->c.resize(T); }
    p->k.insert(p->k.begin() + i, y->k[T - 1]);    // the median goes up into the parent
    p->c.insert(p->c.begin() + i + 1, z);
    y->k.resize(T - 1);
}
void insert(int x) {
    if ((int)root->k.size() == 2 * T - 1) {        // full root: the tree grows by one level
        Node* s = &pool.emplace_back(); s->c.push_back(root); root = s; split(s, 0);
    }
    Node* v = root;
    while (!v->c.empty()) {                        // go down, splitting a full child first
        int i = upper_bound(v->k.begin(), v->k.end(), x) - v->k.begin();
        if ((int)v->c[i]->k.size() == 2 * T - 1) { split(v, i); if (x > v->k[i]) ++i; }
        v = v->c[i];
    }
    v->k.insert(upper_bound(v->k.begin(), v->k.end(), x), x);
}
pair<bool, int> search(int x) {                    // (found, nodes visited)
    Node* v = root;
    for (int visits = 1; ; ++visits) {
        auto it = lower_bound(v->k.begin(), v->k.end(), x);
        if (it != v->k.end() && *it == x) return {true, visits};
        if (v->c.empty()) return {false, visits};
        v = v->c[it - v->k.begin()];
    }
}
string show() {                                    // level by level, levels separated by |
    string out; vector<Node*> lvl{root};
    while (!lvl.empty()) {
        vector<Node*> nxt;
        for (size_t n = 0; n < lvl.size(); ++n) {
            out += n ? " [" : "[";
            for (size_t j = 0; j < lvl[n]->k.size(); ++j) out += (j ? " " : "") + to_string(lvl[n]->k[j]);
            out += "]";
            nxt.insert(nxt.end(), lvl[n]->c.begin(), lvl[n]->c.end());
        }
        lvl = nxt;
        if (!lvl.empty()) out += " | ";
    }
    return out;
}
int main() {
    for (int x : {50, 20, 80, 10, 30, 60, 90, 40, 70, 25}) { insert(x); cout << "insert " << x << ": " << show() << '\n'; }
    for (int x : {70, 35}) {
        auto [found, visits] = search(x);
        cout << "search " << x << ": " << (found ? "found" : "not found") << ", nodes visited = " << visits << '\n';
    }
}

insert 50: [50]
insert 20: [20 50]
insert 80: [20 50 80]
insert 10: [50] | [10 20] [80]
insert 30: [50] | [10 20 30] [80]
insert 60: [50] | [10 20 30] [60 80]
insert 90: [50] | [10 20 30] [60 80 90]
insert 40: [20 50] | [10] [30 40] [60 80 90]
insert 70: [20 50 80] | [10] [30 40] [60 70] [90]
insert 25: [50] | [20] [80] | [10] [25 30 40] [60 70] [90]
search 70: found, nodes visited = 3
search 35: not found, nodes visited = 3

from bisect import bisect_left, bisect_right
T = 2                                      # minimum degree: every node holds 1..3 keys

class Node:
    def __init__(self, keys=None, kids=None):
        self.k, self.c = keys or [], kids or []   # keys, children (empty = leaf)

def split(p, i):                           # p.c[i] is full (2T-1 keys)
    y = p.c[i]
    z = Node(y.k[T:], y.c[T:])             # right half moves to a new node
    p.k.insert(i, y.k[T - 1])              # the median goes up into the parent
    p.c.insert(i + 1, z)
    y.k, y.c = y.k[:T - 1], y.c[:T]

def insert(x):
    global root
    if len(root.k) == 2 * T - 1:           # full root: the tree grows by one level
        root = Node([], [root])
        split(root, 0)
    v = root
    while v.c:                             # go down, splitting a full child first
        i = bisect_right(v.k, x)
        if len(v.c[i].k) == 2 * T - 1:
            split(v, i)
            if x > v.k[i]: i += 1
        v = v.c[i]
    v.k.insert(bisect_right(v.k, x), x)

def search(x):                             # (found, nodes visited)
    v, visits = root, 1
    while True:
        i = bisect_left(v.k, x)
        if i < len(v.k) and v.k[i] == x: return True, visits
        if not v.c: return False, visits
        v, visits = v.c[i], visits + 1

def show():                                # level by level, levels separated by |
    lvl, out = [root], []
    while lvl:
        out.append(" ".join("[" + " ".join(map(str, v.k)) + "]" for v in lvl))
        lvl = [c for v in lvl for c in v.c]
    return " | ".join(out)

root = Node()
for x in [50, 20, 80, 10, 30, 60, 90, 40, 70, 25]:
    insert(x)
    print(f"insert {x}: {show()}")
for x in [70, 35]:
    found, visits = search(x)
    print(f"search {x}: {'found' if found else 'not found'}, nodes visited = {visits}")

insert 50: [50]
insert 20: [20 50]
insert 80: [20 50 80]
insert 10: [50] | [10 20] [80]
insert 30: [50] | [10 20 30] [80]
insert 60: [50] | [10 20 30] [60 80]
insert 90: [50] | [10 20 30] [60 80 90]
insert 40: [20 50] | [10] [30 40] [60 80 90]
insert 70: [20 50 80] | [10] [30 40] [60 70] [90]
insert 25: [50] | [20] [80] | [10] [25 30 40] [60 70] [90]
search 70: found, nodes visited = 3
search 35: not found, nodes visited = 3

৫ · Delete — ধার নেওয়া (borrow) আর জোড়া লাগানো (merge)

Insert-এর বিপদ ছিল node উপচে পড়া; delete-এর বিপদ উল্টো — কোনো node-এ key t − 1-এর নিচে নেমে যাওয়া (underflow). সমাধানের দুটি হাতিয়ার:

• Borrow (ধার, rotation বলেও): কম key-ওয়ালা node-এর পাশের ভাইয়ের অন্তত t টি key থাকলে, parent-এর মাঝের key নামিয়ে আনুন এই node-এ, আর ভাইয়ের কিনারার key-টি তুলে দিন parent-এ। পাশের বাসার কাছ থেকে চিনি ধার নেওয়ার মতো — কিন্তু সরাসরি নয়, বাড়িওয়ালার (parent) মাধ্যমে, যাতে সাজানো ক্রম না ভাঙে।
• Merge (জোড়া): দুই ভাইয়েরই মাত্র t − 1 টি key থাকলে, দুজনকে আর parent-এর মাঝের key-টিকে মিলিয়ে একটি node বানান: (t − 1) + 1 + (t − 1) = 2t − 1 টি key — ঠিক একটি ভরা node. এটি split-এর ঠিক উল্টো কাজ। Parent-এ একটি key কমে।

Insert-এর মতোই এখানেও proactive কৌশল আছে (CLRS): নামার পথে কোনো সন্তানে ঢোকার আগে নিশ্চিত করুন তার অন্তত t টি key আছে — না থাকলে আগেই borrow বা merge. তাহলে শেষে কোনো leaf থেকে একটি key মুছলেও সে t − 1-এর নিচে নামবে না। Merge-এ root-এর শেষ key নেমে গেলে root খালি হয়, আর তার একমাত্র সন্তান নতুন root হয় — tree বেঁটে হয় শুধু ওপর থেকে, ঠিক যেমন লম্বা হয় শুধু ওপর থেকে। নিচে আগের অংশের চূড়ান্ত tree থেকে প্রথমে 90, তারপর 50 মোছা দেখুন:

খরচ. প্রতি স্তরে বড়জোর একটি borrow বা merge, প্রতিটিতে ধ্রুবক সংখ্যক node পড়া-লেখা, তাই delete-ও O(log_t n) disk I/O, CPU O(t log_t n). Delete-এর কোড insert-এর প্রায় দ্বিগুণ লম্বা, আর ভুলের সুযোগ অনেক — তাই সব কেসের বিস্তারিত নিচের বাক্সে রাখলাম; প্রথম পড়ায় borrow আর merge-এর ধারণা বুঝলেই যথেষ্ট।

৬ · B+ tree — সব record leaf-এ, leaf-গুলো শিকলে বাঁধা

সাধারণ B-tree-তে প্রতিটি key-এর সাথে তার পুরো record (বা record-এর ঠিকানা) থাকে, যেকোনো node-এ। ডেটাবেস এর একটি রূপ বেশি পছন্দ করে — B+ tree. পার্থক্য তিনটি:

1. সব record শুধু leaf-এ. Internal node-এ থাকে শুধু separator key আর সন্তানের pointer — যেন একটি বইয়ের সূচিপত্র, যেখানে পুরো অধ্যায় নেই, শুধু পাতার নম্বর।
2. Internal node-এর key-গুলো leaf-এর key-এর কপি. একটি key leaf-এ থাকে, আর হয়তো কোনো internal node-এ separator হিসেবে আবারও। এই পর্বের রীতি: separator s হলে বাঁ subtree-তে সব key < s, ডানে সব key ≥ s.
3. Leaf-গুলো পাশাপাশি pointer দিয়ে জোড়া (প্রায়ই দুই দিকেই) — সাজানো ক্রমে একটি লম্বা শিকল, ঠিক পর্ব ১২-এর linked list-এর মতো।

এর লাভ কী? Internal node-এ record না থাকায় একটি page-এ অনেক বেশি key ধরে — fan-out বাড়ে, উচ্চতা কমে। প্রতিটি খোঁজা leaf পর্যন্ত যায়, তাই খরচ সবসময় সমান আর অনুমানযোগ্য। আর সবচেয়ে বড় লাভ range query-তে: “২০২৪ সালের জানুয়ারির সব লেনদেন” বা WHERE price BETWEEN 22 AND 62. প্রথম key-এর leaf খুঁজে নিন, তারপর শুধু শিকল ধরে ডানে হাঁটুন — ওপরে ওঠানামা নেই।

খরচ. K টি ফলাফলের range query-তে প্রথম leaf পর্যন্ত O(log_B N) read, তারপর প্রতিটি leaf-এ প্রায় B টি key, তাই আরও O(K/B + 1) read — মোট O(log_B N + K/B) I/O. একটি key-এর জন্য একটি read নয়, এক page ভর্তি key-এর জন্য একটি read. আর leaf-গুলো যদি ডিস্কে পাশাপাশি রাখা থাকে, শিকল ধরে হাঁটা প্রায় sequential read — hard disk-এ এটি এলোমেলো read-এর চেয়ে বহু গুণ দ্রুত।

৭ · Fan-out আর উচ্চতার হিসাব — ডেটাবেস কেন ৩–৪ ধাপে খোঁজে

B+ tree-র আসল শক্তি বোঝা যায় সংখ্যায়। ধরুন প্রতিটি node (একটি page) f টি entry ধরে — internal node-এ f টি সন্তান, leaf-এ f টি record. তাহলে ১ স্তরে f টি, ২ স্তরে f² টি, L স্তরে f^L টি record. f = ৫০০ হলে ৩ স্তরে 500³ = 1.25 × 10⁸ — প্রায় সাড়ে বারো কোটি record! নিচের ছোট প্রোগ্রামটি কয়েকটি fan-out-এর জন্য দেখায়, n টি record-এর জন্য কয় স্তর লাগে (সবচেয়ে ছোট L, যাতে f^L ≥ n):

#include <cstdio>
#include <initializer_list>
// Levels L needed so that f^L >= n: each node (one disk page) holds f entries.
int levels(unsigned long long f, unsigned long long n) {
    int L = 0;
    for (unsigned long long cap = 1; cap < n; cap *= f) ++L;
    return L;
}
int main() {
    std::printf("fan-out | n=10^6 | n=10^9 | n=10^12 | entries in 3 levels\n");
    for (unsigned long long f : {2ULL, 16ULL, 100ULL, 500ULL, 1000ULL}) {
        std::printf("%7llu | %6d | %6d | %7d | %llu\n", f, levels(f, 1000000ULL),
                    levels(f, 1000000000ULL), levels(f, 1000000000000ULL), f * f * f);
    }
    // a lookup reads one page per level; with the top 2 levels cached in RAM:
    int L = levels(500, 1000000000ULL);
    std::printf("fan-out 500, n=10^9: %d levels, %d disk reads if top 2 levels are cached\n", L, L - 2);
}

fan-out | n=10^6 | n=10^9 | n=10^12 | entries in 3 levels
      2 |     20 |     30 |      40 | 8
     16 |      5 |      8 |      10 | 4096
    100 |      3 |      5 |       6 | 1000000
    500 |      3 |      4 |       5 | 125000000
   1000 |      2 |      3 |       4 | 1000000000
fan-out 500, n=10^9: 4 levels, 2 disk reads if top 2 levels are cached

ডেটাবেস আর file system-এ B-tree পরিবার

এই কারণেই প্রায় প্রতিটি relational ডেটাবেসের ডিফল্ট index B-tree পরিবারের। নামগুলো সাবধানে বলি — প্রতিটি সিস্টেম নিজের মতো করে রূপ বদলেছে, আর documentation-এ প্রায়ই সবকিছুকেই সাধারণভাবে “B-tree” বলা হয়:

পেছনের কারণ একটাই: এই সিস্টেমগুলোকে কোটি কোটি সাজানো key রাখতে হয়, যার বেশিরভাগ ডিস্কে; খোঁজা, insert, delete আর রেঞ্জ scan সবই দ্রুত চাই; আর একটি ভাঙা লেখা (যেমন লেখার মাঝপথে বিদ্যুৎ চলে যাওয়া) যেন পুরো কাঠামো নষ্ট না করে। Hash table (পর্ব ৩২) একটি key খুঁজতে আরও দ্রুত হতে পারে, কিন্তু ক্রম রাখে না — রেঞ্জ, ORDER BY বা “এই prefix দিয়ে শুরু” প্রশ্নে অচল। বাংলাদেশের কোনো ব্যাংক যখন আপনার গত তিন মাসের statement দেখায়, পেছনে খুব সম্ভবত ঠিক এই range scan-টিই চলে।

৮ · পরিবারের অন্যরা — 2-3 tree, red-black আর B* tree

2-3 tree হলো সবচেয়ে ছোট B-tree: প্রতিটি internal node-এ ১টি key আর ২টি সন্তান (“2-node”), অথবা ২টি key আর ৩টি সন্তান (“3-node”), আর সব leaf একই গভীরতায়। Knuth-এর রীতিতে order 3. John Hopcroft ১৯৭০ সালে এই ধারণা দেন — B-tree-র প্রকাশের প্রায় একই সময়ে, কিন্তু আলাদাভাবে এবং মেমরির ভেতরের ভারসাম্যপূর্ণ tree হিসেবে। Insert-এ কোনো 3-node-এ তৃতীয় key এলে সে মাঝেরটিকে ওপরে পাঠিয়ে ভাগ হয় — ঠিক B-tree-র split.

এক ধাপ বড় হলো t = 2-এর B-tree, অর্থাৎ 2-3-4 tree — যার ওপর অংশ ৪-এ insert চালালেন। এর সাথে পর্ব ২৯-এর red-black tree-এর সম্পর্ক অবাক করার মতো: প্রতিটি red-black tree আসলে একটি 2-3-4 tree-র binary ছদ্মবেশ. 2-3-4 tree-র প্রতিটি node-কে ১–৩টি binary node-এ ভাঙুন: মাঝের key কালো, বাকিরা তার লাল সন্তান।

2-3-4 node            red-black রূপ (R = লাল, B = কালো)

[50]          →           50B

[20 50]       →           50B              (অথবা 20B, ডানে 50R)
                         /
                       20R

[20 50 80]    →           50B
                         /    \
                       20R    80R

এই চোখে দেখলে red-black-এর নিয়মগুলো আর মুখস্থ করতে হয় না। “লাল node-এর সন্তান লাল নয়” মানে একটি B-tree node-এ ৩টির বেশি key নেই। “root থেকে প্রতিটি leaf-এ কালো node-এর সংখ্যা সমান” মানে B-tree-র সব leaf একই গভীরতায়. Red-black-এ color flip হলো 2-3-4 tree-র 4-node split, আর rotation হলো একটি B-tree node-এর ভেতরে key-গুলোর সাজ বদলানো। আর উচ্চতা: B-tree-র উচ্চতা log n-এর কাছাকাছি, প্রতিটি স্তরে বড়জোর একটি লাল node যোগ হয় — তাই red-black-এর উচ্চতা ≤ 2 log₂(n + 1). ২০০৮ সালে Robert Sedgewick 2-3 tree-র সাথে ঠিক এক-এক মিলের একটি সরল রূপ দেন — left-leaning red-black tree.

B* tree (Knuth ১৯৭৩ সালে বর্ণনা করেন) জায়গা আরও ভালোভাবে ভরতে চায়। সাধারণ B-tree-তে node উপচালেই ভাগ হয়, ফলে দুটি প্রায়-অর্ধেক node. B*-তে উপচে পড়লে আগে পাশের ভাইয়ের সাথে key ভাগাভাগি করে নেয়; ভাইও ভরা হলে দুটি ভরা node মিলে তিনটি node হয় (২ থেকে ৩ split). ফল: root ছাড়া প্রতিটি node অন্তত প্রায় দুই-তৃতীয়াংশ ভরা, তাই একই ডেটায় node কম, fan-out বেশি, উচ্চতা কখনো কখনো এক স্তর কম। দাম: কোড আরও জটিল, প্রতিটি insert-এ ভাইয়ের page-ও পড়তে-লিখতে হতে পারে।

৯ · AI-এর যুগে B-tree — সংজ্ঞা গুলিয়ে ফেলা আর split-এর off-by-one

“একটি B-tree insert লিখে দাও” — AI দ্রুতই লিখবে, আর ছোট পরীক্ষায় চলবেও। B-tree-র ভুল লুকিয়ে থাকে তিন জায়গায়: সংজ্ঞায় (t নাকি order m), split-এর index-এ (median কোনটি, কোন সন্তান কোথায় যায়), আর delete-এর বিরল কেসে (internal node থেকে মোছা, root খালি হওয়া)। ছোট ইনপুটে এই শাখাগুলো প্রায়ই চলেই না, তাই ভুল ধরা পড়ে না। আর ডেটাবেস বা file system সম্পর্কে AI প্রায়ই আত্মবিশ্বাসী কিন্তু ভুল দাবি করে — নির্দিষ্ট সিস্টেমের কথা সবসময় তার অফিসিয়াল documentation-এ মিলিয়ে নিন।

B-tree-র কোড আর উত্তরে AI সাধারণত যেসব ভুল করে

B-tree-র কোড যাচাইয়ের চেকলিস্ট

• কোন রীতি (t নাকি order m) ব্যবহার করছি তা কোডের শুরুতে comment-এ লিখেছি, আর সর্বোচ্চ ও সর্বনিম্ন key-সংখ্যা সেই রীতিতে মিলিয়েছি
• একটি check() ফাংশন লিখেছি: প্রতিটি node সাজানো, key-সংখ্যা সীমার মধ্যে, separator subtree-গুলোকে ঠিক ভাগ করে, আর সব leaf একই গভীরতায় — প্রতিটি অপারেশনের পর assert
• Edge case চালিয়েছি: খালি tree, এক key, ডুপ্লিকেট key, বাড়তে ও কমতে থাকা ক্রম, root split আর root খালি হওয়া
• হাজারটি এলোমেলো insert/delete/search-এর ফল std::set বা সাজানো list-এর (brute force) সাথে মিলিয়ে stress testing করেছি
• ছোট t (২ ও ৩) দিয়ে পরীক্ষা করেছি — বড় t-তে split কম হয়, তাই ভুল লুকিয়ে থাকে
• AI যে ডেটাবেস বা file system-এর দাবি করেছে, তা অফিসিয়াল documentation-এ মিলিয়েছি