B+ Tree Index — database index-এর কারখানা

আগে এটা বুঝি

গত লেসন শেষ হয়েছিল এই লাইনে — Buffers: shared hit=7 read=0। Warm pool- এ point query মাত্র ৭টা page ছুঁয়েছিল — তার ৩–৪টাই ছিল একটা B+ tree index-এর। algorithms module-এ B+ tree-র গণিত দেখেছি, আজ তার কারখানা: PostgreSQL-এর nbtree। প্রশ্ন: index disk-এ কেমন file, scan কোন ধাপে কোন page পড়ে, INSERT কেন প্রতি index-এ খাজনা দেয়, composite order কীভাবে?

মূল ধারণা

B+ tree — ঝালিয়ে নেওয়া দুই সিদ্ধান্ত

গত লেসনের দুই সিদ্ধান্ত:

Data শুধু leaf-এ। Internal key মাত্র signpost — fanout বাড়ে, height কমে।
Leaf-রা linked list-এ। Range scan = এক descent + সমান্তরাল হাঁটা।

Workload (range, sort, prefix) দ্বিতীয় সিদ্ধান্তেই জেতে — তাই PostgreSQL, InnoDB, SQLite সবাই B+-ই চালায়।

Index = আলাদা এক relation

PostgreSQL-এ index table-এর ‘অংশ’ না — নিজস্ব relfilenode file। প্রতিটা leaf entry = key + TID — সেই tuple- ঠিকানা ctid = (block, offset)। Slotted-page promise মনে আছে? Tuple relocate হলেও ctid অটল — indirection-এর সুদ এখানেই ফেরত আসে।

nbtree-র page anatomy

nbtree — native B-tree, PostgreSQL-র B-tree access method-এর আসল নাম। Page-রা চার চরিত্রে:

Page	ভেতরে থাকে
Metapage (block 0)	magic, version, root block-number, level
Root	descent-এর শুরু; cached থাকে buffer pool-এ
Internal	শুধু separator key + child pointer
Leaf	sorted key + TID + `btpo_next` (ডান ভাই) + high key

High key — non-rightmost প্রতিটা page-এর ItemId[1]-এ data না, key- সীমার ঘোষণা (“সব key এর চেয়ে ছোট”); split-এ বাঁ-ভাগ নতুনটা পায়, ডান-ভাগ পুরনোটা উত্তরাধিকারে।

Deduplication (v13+, 2020): duplicate-দের আগের লাখ-আলাদা-entry-র বদলে এখন এক posting list — এক key + TID-array। Space কমে, split কমে, write amplification কমে (unique index-এ dedup নেই — duplicate-ই নেই!)।

Index scan-এর পুরো পথ

Index Scan — query থেকে row পর্যন্ত

Metapage (pool-এ cached)root block-number এখান থেকে — disk ছোঁয়া লাগে না
Descent: root → internalপ্রতি page-এ binary search; fanout ~১০০–৩০০ তাই ২–৪ hop
Leaf: first qualifying keybinary search-এ scan-start; বাকি match ডানদিকে
Leaf-chain walkrange হলে btpo_next ধরে ডানে — sequential page-read
Heap fetch via ctidপ্রতি match-এ heap page — random I/O, খরচের রাজা এখানেই

শেষ ধাপটাই ব্যথা: row-রা heap-এ এলোমেলো — ১০০ match মানে ১০০ random heap read। Planner-র দুই প্রশ্ন: “index আছে?” আর “match-রা heap-এ কতটা গুছিয়ে আছে?”

Covering index — INCLUDE clause

Heap-trip এড়ানোর অস্ত্র: CREATE INDEX ON big (cust_id) INCLUDE (amount)। amount key না — sort/search/uniqueness-তে ঢোকে না, শুধু leaf-payload। Query দুটোই চাইলে heap ছোঁয়ার প্রয়োজনই শেষ।

Index-only scan — visibility map-এর গোপন

MVCC visibility (xmin/xmax) বাসা heap-header-এ — index entry জানে না row visible কি না। উত্তর visibility map (_vm sidecar): VACUUM all-visible page-এ bit সেট করে, IOS bit বিশ্বাস করে heap skip করে; unset হলে বাধ্যে heap-fetch (Heap Fetches)। IOS vacuum-এর সন্তান — bulk UPDATE-এর পরে অন্ধ, vacuum-এ চোখ ফেরত।

Write amplification — প্রতি INSERT-এর খাজনা

Table-এ N index থাকলে প্রতিটা INSERT = heap insert + N×(descend + leaf write + WAL)। হিসাব: row ১০০ B, entry ~২০ B, ৫ index → physical ≈ ১০০ + ৫×(~৭০) ≈ ৪৫০ B — amplification ~৪.৫×। UPDATE-ও চতুর: indexed column বদলালে dead + new entries সব index-এ; না বদলালে — HOT update, index ছোঁয়ই না (MVCC লেসনে বিস্তারিত)।

Delete ও bloat

DELETE row-কে মারে, entry-কে না — LP_DEAD mark বা vacuum-অপেক্ষা। Vacuum জায়গা reusable করে, page-ফাঁকা-গর্ত আর order ফেরায় না; ভেতরে ৩০–৪০% dead অথচ size পূর্ণ — এই রোগ bloat। ঔষধ REINDEX CONCURRENTLY।

Composite index — leftmost prefix rule

(a, b, c) index = dictionary sorted by a, then b, then c:

Query predicate	`(a,b,c)` খাটে?
`a = ? AND b = ?`	পুরোপুরি (একা `a = ?`-ও)
`a = ? AND b > ?`	a equality + b range
`b = ?`	না — b-রা a-ভাঙা ছড়ানো
`a = ? AND c = ?`	a পর্যন্ত; c শুধু filter, range নয়

নিয়ম: leftmost prefix — leading columns equality-তে থাকলেই পরের column-এর range/sort-ও index-এই মেটে। মন্ত্র: equality আগে, range শেষে; PostgreSQL-এ skip-scan নেই, তাই b = ? একা এখানে চলবে না।

ভেতরে কী ঘটছে

pageinspect দিয়ে nbtree খোলা

Storage লেসনে heap page খুলেছিলাম; nbtree-র নিজস্ব চাবিও আছে (pageinspect):

CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT * FROM bt_metap('big_cust');
SELECT itemoffset, itemlen, ctid, data
FROM bt_page_items('big_cust', 12);        -- একটা non-rightmost leaf

 bt_metap: magic 340322 | version 4 | root 3 | level 2 | fastroot 3

 bt_page_items (block 12):
 itemoffset |   ctid   |       data
 ------------+----------+---------------------------
           1 |          | 96 00 ...               ← HIGH KEY: itemlen ছোট, ctid খালি
           2 | (4,7)    | 69 00 00 00 ...         ← key=105 → heap (4,7)
           3 | (4,9)    | 76 00 00 00 ...         ← key=118 → heap (4,9)

পড়ার চাবি: metapage-এ root=3; leaf-এর itemoffset 1-ই high key; প্রতিটা data-item-এর ctid column-ই heap-ঠিকানা।

উদাহরণ

একটা query-র পুরো journey

Table orders(id, cust_id, amount, status) — ২০ লাখ row, index (cust_id) INCLUDE (amount)। Query SELECT sum(amount) ... WHERE cust_id = 42;, warm pool:

1. Metapage (hit)            → root = block 3
2. Root block 3 (hit)        → binary search: 42 → child 7
3. Internal block 7 (hit)    → child 12
4. Leaf block 12 (hit)       → প্রথম 42 @ offset 5
5. Chain walk 12 → 13        → ৪৩ entry; VM bit=1 → heap trip শূন্য!

EXPLAIN বলবে: Index Only Scan ... Heap Fetches: 0, Buffers: shared hit=6 — ২০ লাখ row-র table-এ ৬ page। এবার SELECT sum(amount), status ... — status index-এ নেই → প্রতি row-এ heap fetch → Index Scan, Buffers: shared hit=~50। এক column INCLUDE-এ থাকা-না-থাকার ফারাক: ৬ বনাম ৫০ buffer। Range-ও একই সুখ: (cust_id, created_at)-এ BETWEEN + ORDER BY — descent + chain-walk, ORDER BY ফ্রি; উল্টো index হলে leftmost-prefix ভাঙে — Seq Scan।

ছবিতে

 index file 26191                       heap file 16385
┌───────────────────┐
│ block 0 META      │ magic·version·ROOT=3·level=2
└─────────┬─────────┘
          ▼
┌───────────────────┐
│ block 3 ROOT      │ keys: [105 │ 210 │ 340]  ← শুধু signpost
└───┬─────┬─────┬───┘
    ▼     ▼     └────────────┐
┌──────────────┐  ┌──────────────────┐
│ internal 7   │  │ ... internals    │
│ sep[150│203] │  │                  │
└─┬────┬───┬───┘  └──────────────────┘
  ▼    ▼   └────────┐
┌────────────────────┐ next ┌────────────────────────┐
│ leaf 12  HIKEY=150 │─────▶│ leaf 13  HIKEY=203     │──▶ ...
│ (105, ctid(4,7))   │      │ (160, ctid(9,2))       │
│ (118, ctid(4,9))   │      │ (171, ctid(2,5))       │
│ (133, ctid(7,1))   │      │ (188, ctid(11,4))      │
└────────────────────┘      └────────────────────────┘

point 171: meta→root→int7→leaf13 (৪ page) + heap (2,5) (১ page)
range 105..190: descent + leaf12→13 chain walk (sequential!)

Index Scan vs Index Only Scan: IOS প্রতি heap PAGE-এ visibility-map bit
দেখে — all-visible হলে heap ছোঁয়াই না; VACUUM-ই bit সেট করে।

nbtree-র page-জগৎ — metapage থেকে leaf-chain, leaf entry heap-এর ctid ধরে:

নিজে চালিয়ে দেখুন

EXPERIMENT

CREATE INDEX-এর স্কেল, তিন scan-plan-এর buffer-বিল, আর unused-index শিকার

PostgreSQL 14+ (psql; Docker caveat নিচে)· ২৫ মিনিট

ধাপ ০ — server: docker run --rm -d --name pg-lab -e POSTGRES_PASSWORD=lab -p 5432:5432 postgres:16, তারপর docker exec -it pg-lab psql -U postgres। \timing on।

ধাপ ১ — CREATE INDEX timing vs size: একই ছাঁচে তিন মাপের table — generate_series(1, N)-এর N বসিয়ে s/m/l বানান (uid, payload md5 সহ), তারপর:

CREATE TABLE l AS SELECT g AS id, (g % 50000)::int AS uid,
       md5(g::text) AS payload FROM generate_series(1, 4000000) g;
CREATE INDEX l_idx ON l (uid);

N = 100k / 1M / 4M-এ মোটামুটি ~৩০ ms → ~২৫০ ms → ~১১০০ ms — Row ৪০×, সময় ~৩৫×, প্রায় linear। এজন্যই peak hour-এ বিশাল index বানানো যায় না; CREATE INDEX CONCURRENTLY ধীর কিন্তু lock নেয় না।

ধাপ ২ — তিন plan, তিন বিল: বড় table-টাই arena:

VACUUM ANALYZE l;                          -- VM তৈরি — IOS-এর প্রাণ!
EXPLAIN (ANALYZE, BUFFERS)
  SELECT sum(id) FROM l WHERE uid = 42;    -- → Index Scan
CREATE INDEX l_cov ON l (uid) INCLUDE (id);
VACUUM l;                                  -- fresh VM
EXPLAIN (ANALYZE, BUFFERS)
  SELECT sum(id) FROM l WHERE uid = 42;    -- → Index Only Scan
SET enable_indexscan = off; SET enable_indexonlyscan = off;
EXPLAIN (ANALYZE, BUFFERS)
  SELECT sum(id) FROM l WHERE uid = 42;    -- → জোর করে Seq Scan
RESET ALL;

মোটামুটি প্রত্যাশিত (hardware-ভেদে সংখ্যা বদলাবে, ratio নয়):

Index Scan:      Buffers: shared hit≈48     Execution Time: ~0.09 ms
Index Only Scan: Buffers: shared hit=8  Heap Fetches: 0   ~0.04 ms
Seq Scan:        Buffers: shared hit≈27000  Rows Removed by Filter: 3999959

~৪৮ hit = ৪ tree + ~৪৪ heap page (match-রা ছড়ানো); INCLUDE-সংস্করণে heap-part শূন্য; Seq Scan পুরো table (~২১০ MB ÷ ৮ KB ≈ ২৭K page) পড়তেই বাধ্য।

ধাপ ৩ — unused-index hunt: আগে অপরাধী বানান, তারপর বিচার:

CREATE INDEX l_payload ON l (payload);   -- decoy: কেউ কখনো ব্যবহার করবে না
SELECT count(*) FROM l WHERE uid = 7;    -- কিছু real কাজ
SELECT indexrelname, idx_scan,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes WHERE relname = 'l'
ORDER BY idx_scan ASC;

মোটামুটি: l_payload | 0 | 84 MB — বিপরীতে l_idx | 142 | 43 MB। idx_scan = 0 অথচ ৮৪ MB — production-এ এই index প্রতি INSERT-এ খাজনা নেয়, কিছুই ফেরত দেয় না। SELECT pg_stat_reset(); দিয়ে counter শূন্য করে সপ্তাহ-লম্বা window মাপা প্রতি-মাসের housekeeping ritual।

এটা কী প্রমাণ করে

CREATE INDEX প্রায় linearly scale করে; একই query Seq Scan-এ ~২৭,০০০ buffer খায় যেখানে Index Only Scan-এ ~৮ — EXPLAIN (ANALYZE, BUFFERS)-এর shared-hit counter-ই theory-র প্রমাণ; pg_stat_user_indexes দেখায় কোন index বেতন খেয়ে বসে আছে অথচ একবারও ব্যবহৃত হয়নি।

নিজে বানান

BUILD IT

DiskSimulatedBPlusTree — bytearray-'disk'-এ fixed 256-byte node, split/borrow/merge সহ

Python · ●●●●○

'disk' = bytearray; প্রতিটা node 256-byte fixed record — struct pack/unpack
capacity math: internal max 40 key (fanout 41), leaf max 31 entry
insert: leaf overflow → split, separator copy-up, root-split-এ height++
delete: underflow → আগে borrow (separator rotate), না হলে merge, parent propagate
range_scan(lo,hi): descent + leaf-chain walk
stats(): height, page count, fill %, splits, merges, disk-read counter

প্রতিটা node byte-buffer-এ serialize হয়, যেমন nbtree ৮ KB page-এ থাকে। Capacity: internal ৪ B header + 40×4 B key + 41×2 B child = 246 B ≤ 256; leaf ৪ + 31×8 B = 252 B; worst merge 19+1+20 = 40 key — ঠিক capacity-তে:

import bisect, random, struct
PAGE, DISK_PAGES = 256, 4096           # প্রতিটা node ঠিক এক 'page'
MAX_INT, MAX_LEAF = 40, 31             # pack: internal 246 B, leaf 252 B
MIN_INT, MIN_LEAF = MAX_INT // 2, MAX_LEAF // 2
class DiskSimulatedBPlusTree:
    """bytearray-'disk'-এ fixed-size node; প্রতিটা access আসল page read/write"""
    def __init__(self):
        self.disk = bytearray(PAGE * DISK_PAGES)
        self.next_free = 1                  # page 0 = metapage
        self.splits = self.merges = self.reads = 0
        self.height = 1
        self._set_meta(self._alloc(True))
    def _alloc(self, leaf):
        addr, self.next_free = self.next_free, self.next_free + 1
        assert addr < DISK_PAGES, 'disk full'
        self._write(addr, {'leaf': leaf, 'keys': [], 'vals': [], 'kids': [], 'next': 0})
        return addr
    def _write(self, addr, nd):
        buf = struct.pack('>BBH', nd['leaf'], len(nd['keys']), nd['next'])
        buf += b''.join(struct.pack('>i', x) for x in nd['keys'] + nd['vals'])
        buf += b''.join(struct.pack('>H', c) for c in nd['kids'])
        assert len(buf) <= PAGE, f'node {addr}: {len(buf)} B > {PAGE} B'
        base = addr * PAGE
        self.disk[base:base + len(buf)] = buf
    def _read(self, addr):
        self.reads += 1
        base = addr * PAGE
        leaf, n, nxt = struct.unpack_from('>BBH', self.disk, base)
        off = base + 4
        keys = list(struct.unpack_from(f'>{n}i', self.disk, off)); off += 4 * n
        if leaf:
            vals = list(struct.unpack_from(f'>{n}i', self.disk, off))
            return {'leaf': True, 'keys': keys, 'vals': vals, 'kids': [], 'next': nxt}
        kids = list(struct.unpack_from(f'>{n + 1}H', self.disk, off))
        return {'leaf': False, 'keys': keys, 'vals': [], 'kids': kids, 'next': nxt}
    def _set_meta(self, root):
        struct.pack_into('>H', self.disk, 0, root)
    def _root(self):
        return struct.unpack_from('>H', self.disk, 0)[0]
    def _descend(self, key):
        addr, path = self._root(), []
        while True:
            nd = self._read(addr)
            path.append(addr)
            if nd['leaf']:
                return nd, addr, path
            addr = nd['kids'][bisect.bisect_right(nd['keys'], key)]
    def get(self, key):
        nd, _, _ = self._descend(key)
        i = bisect.bisect_left(nd['keys'], key)
        return nd['vals'][i] if i < len(nd['keys']) and nd['keys'][i] == key else None
    def range_scan(self, lo, hi):
        nd, _, _ = self._descend(lo)
        i, out = bisect.bisect_left(nd['keys'], lo), []
        while True:
            while i < len(nd['keys']):
                if nd['keys'][i] > hi:
                    return out
                out.append((nd['keys'][i], nd['vals'][i])); i += 1
            if not nd['next']:
                return out
            nd, i = self._read(nd['next']), 0      # leaf-chain-এ ডানে!
    def put(self, key, val):
        nd, addr, path = self._descend(key)
        i = bisect.bisect_left(nd['keys'], key)
        if i < len(nd['keys']) and nd['keys'][i] == key:   # overwrite
            nd['vals'][i] = val
            return self._write(addr, nd)
        nd['keys'].insert(i, key); nd['vals'].insert(i, val)
        if len(nd['keys']) <= MAX_LEAF:
            return self._write(addr, nd)
        mid = len(nd['keys']) // 2                 # leaf split: separator COPY-up
        right = self._alloc(True)
        r = {'leaf': True, 'keys': nd['keys'][mid:], 'vals': nd['vals'][mid:], 'kids': [], 'next': nd['next']}
        nd = {'leaf': True, 'keys': nd['keys'][:mid], 'vals': nd['vals'][:mid], 'kids': [], 'next': right}
        self._write(right, r); self._write(addr, nd)
        self.splits += 1
        self._push_up(path[:-1], addr, r['keys'][0], right)
    def _push_up(self, path, child, sep, new_child):
        while True:
            if not path:                           # root split — height বাড়ে শুধু এখানে
                root = self._alloc(False)
                self._write(root, {'leaf': False, 'keys': [sep], 'vals': [],
                                   'kids': [child, new_child], 'next': 0})
                self._set_meta(root); self.height += 1
                return
            paddr = path.pop()
            par = self._read(paddr)
            j = par['kids'].index(child)
            par['keys'].insert(j, sep); par['kids'].insert(j + 1, new_child)
            if len(par['keys']) <= MAX_INT:
                return self._write(paddr, par)
            m = len(par['keys']) // 2              # internal split: median MOVE-up
            up = par['keys'][m]
            right = self._alloc(False)
            self._write(right, {'leaf': False, 'keys': par['keys'][m + 1:], 'vals': [],
                                'kids': par['kids'][m + 1:], 'next': 0})
            self._write(paddr, {'leaf': False, 'keys': par['keys'][:m], 'vals': [],
                                'kids': par['kids'][:m + 1], 'next': 0})
            self.splits += 1
            child, sep, new_child = paddr, up, right
    def delete(self, key):
        nd, addr, path = self._descend(key)
        i = bisect.bisect_left(nd['keys'], key)
        assert i < len(nd['keys']) and nd['keys'][i] == key, f'{key} নেই!'
        del nd['keys'][i]; del nd['vals'][i]
        self._write(addr, nd)
        self._fix(path[:-1], addr)                 # ancestors পাঠান, leaf নয়
    def _fix(self, path, addr):
        while True:
            nd = self._read(addr)
            if not path:                           # root: single-child internal → নেমে আসো
                if not nd['leaf'] and len(nd['kids']) == 1:
                    self._set_meta(nd['kids'][0]); self.height -= 1; self.merges += 1
                return
            if len(nd['keys']) >= (MIN_LEAF if nd['leaf'] else MIN_INT):
                return                             # underflow নেই
            paddr = path.pop()
            par = self._read(paddr)
            j = par['kids'].index(addr)
            for sj in (j - 1, j + 1):              # আগে borrow — দুই দিক
                if 0 <= sj < len(par['kids']):
                    sib = self._read(par['kids'][sj])
                    if len(sib['keys']) > (MIN_LEAF if sib['leaf'] else MIN_INT):
                        if sj < j:
                            self._pull_from_left(par, j - 1, nd, sib)
                        else:
                            self._push_from_right(par, j, nd, sib)
                        self._write(par['kids'][sj], sib)
                        self._write(addr, nd); self._write(paddr, par)
                        return
            k = max(0, j - 1)                      # দুই ভাই-ই দরিদ্র → merge
            left = self._read(par['kids'][k]); right = self._read(par['kids'][k + 1])
            if left['leaf']:
                left['keys'] += right['keys']; left['vals'] += right['vals']
                left['next'] = right['next']
            else:                                  # separator parent থেকে নেমে আসে
                left['keys'] += [par['keys'][k]] + right['keys']
                left['kids'] += right['kids']
            self._write(par['kids'][k], left)
            del par['keys'][k]; del par['kids'][k + 1]
            self._write(paddr, par); self.merges += 1
            addr = paddr                           # parent-ই এবার underflow হতে পারে
    def _pull_from_left(self, par, k, cur, sib):   # ভরাট বাঁ-ভাই ধার দেয়
        if sib['leaf']:
            cur['keys'].insert(0, sib['keys'].pop()); cur['vals'].insert(0, sib['vals'].pop())
            par['keys'][k] = cur['keys'][0]
        else:
            cur['keys'].insert(0, par['keys'][k]); cur['kids'].insert(0, sib['kids'].pop())
            par['keys'][k] = sib['keys'].pop()
    def _push_from_right(self, par, k, cur, sib):  # ভরাট ডান-ভাই ধার দেয়
        if sib['leaf']:
            cur['keys'].append(sib['keys'].pop(0)); cur['vals'].append(sib['vals'].pop(0))
            par['keys'][k] = sib['keys'][0]
        else:
            cur['keys'].append(par['keys'][k]); cur['kids'].append(sib['kids'].pop(0))
            par['keys'][k] = sib['keys'].pop(0)
    def stats(self):
        pages = leaves = fill = 0
        deepest, stack = 1, [(self._root(), 1)]
        while stack:
            a, d = stack.pop()
            nd = self._read(a)
            pages += 1; deepest = max(deepest, d)
            fill += len(nd['keys']) / (MAX_LEAF if nd['leaf'] else MAX_INT)
            if nd['leaf']:
                leaves += 1
            else:
                stack += [(c, d + 1) for c in nd['kids']]
        return (f'height={self.height} pages={pages}(leaf {leaves}) fill={fill / pages * 100:.0f}%'
                f' splits={self.splits} merges={self.merges} disk-reads={self.reads}')
if __name__ == '__main__':
    random.seed(7)
    t = DiskSimulatedBPlusTree()
    keys = random.sample(range(100_000), 600)
    for k in keys:
        t.put(k, k * 10)
    assert t.range_scan(-10**9, 10**9) == [(k, k * 10) for k in sorted(keys)]
    print('600 random inserts :', t.stats())
    dead = set(sorted(keys)[::2])                  # প্রতি দ্বিতীয়টা মুছুন
    for k in sorted(dead):
        t.delete(k)
    alive = sorted(set(keys) - dead)
    assert t.range_scan(-10**9, 10**9) == [(k, k * 10) for k in alive]
    assert t.get(sorted(dead)[0]) is None and t.get(alive[0]) == alive[0] * 10
    print('half deleted       :', t.stats())       # borrow + merge ঘটেছে?

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

600 random inserts : height=2 pages=27(leaf 26) fill=74% splits=25 merges=0 disk-reads=1246
half deleted       : height=2 pages=18(leaf 17) fill=56% splits=25 merges=9 disk-reads=2745

পাঠ: random ৬০০ key-ও height ২ — fanout-এর শক্তি; অর্ধেক delete-এ pages 27→18, merges=9, অথচ leaf-chain অক্ষত — range_scan assertion-ই প্রমাণ।

নিজে বাড়ান: (১) sorted-input attack — monotonic put-এ split pattern, BST-র degenerate-chain এখানে অসম্ভব কেন; (২) duplicate-key posting list — nbtree dedup-এর mini সংস্করণ; (৩) freelist — freed-page reuse।

বাস্তব সিস্টেমে

Production-এ nbtree

PostgreSQL: ~৯৫% index nbtree; REINDEX CONCURRENTLY bloat-cure; PG13 dedup duplicate-heavy index কয়েকগুণ ছোট করেছে।
InnoDB: secondary leaf-এ primary key বসে — PK যত ছোট, সব secondary তত ছোট (UUID-PK-র অভিশাপ)। SQLite: প্রতিটা index এক B+ tree।
Filesystems: XFS extent index, APFS OMAP — একই anatomy-পাঠ।

Ritual: মাসে একবার idx_scan=0 শিকার + pgstattuple bloat% — লক্ষ লাখ বাঁচে।

যে ভুলগুলো সবাই করে

“Index মানেই speed — যতগুলো index তত ভালো।”

প্রতিটা index প্রতি INSERT/UPDATE-এ খাজনা চায় — descend + leaf write + WAL; ৮-index table-এ insert-path প্রায় ৯ tree-touch। সিদ্ধান্ত হয় workload-ratio দিয়ে, আবেগে নয়।

“Covering index থাকলেই index-only scan হবে।”

Column coverage এক শর্ত; দ্বিতীয় শর্ত visibility map — bulk UPDATE-এর পরে Heap Fetches আকাশে; vacuum চলার আগে IOS ‘নামের’ IOS-ই।

“Composite index (a,b,c) — যেকোনো column দিয়ে খুঁজলেই কাজ করবে।”

Leftmost-prefix rule: b = ? একা এই index ছুঁতেই পারবে না — b-রা a-ভাঙা ছড়ানো। Column order design = আপনার query-set-এর mirror।

“DELETE দিলে index entry-ও সঙ্গে সঙ্গে মুছে যায়, জায়গা ফেরত আসে।”

Entry শুধু dead-mark হয়; vacuum reusable করে, page-fragmentation থেকেই যায় — আসল ‘ফেরত’ REINDEX CONCURRENTLY, আর সেটাও lock-window চায়।

বুঝেছেন কি না দেখুন

nbtree file-এর চার ধরনের page আর metapage-এর তিনটা জরুরি field? High key কোথায় বসে, কী ঘোষণা করে?

স্মরণ

Metapage, root, internal, leaf। Metapage: magic/version, root block-number, level। High key = non-rightmost page-র ItemId[1] — “এই page-এর সব key এর চেয়ে ছোট”; split-এ বাঁ-ভাগ নতুনটা পায়, ডান-ভাগ পুরনো।

Index (city, age, salary)। কোন query index খাটে, কোন মাত্রায়: (ক) salary > 100000; (খ) city = 'Dhaka' AND age = 30; (গ) city = 'Dhaka' AND salary > 100000; (ঘ) ORDER BY city, age?

প্রয়োগ

(ক) না — leftmost নয়। (খ) পুরোপুরি। (গ) city equality পর্যন্ত; salary শুধু filter — range নয়। (ঘ) হ্যাঁ — Sort node লাগবে নा।

Nightly ETL বড় এক UPDATE চালাল; সকালে index-only scan-এর Heap Fetches শূন্য থেকে হাজারে। কী ভাঙল, কী ঠিক করবে?

যুক্তি

UPDATE touched page-গুলোর all-visible status নিল — VM bits clear, IOS এখন প্রতি page-এ heap-verify করে। ঠিক করবে VACUUM — VM আবার সেট হলে Fetches শূন্য। Index অক্ষত; রোগ heap-visibility-র।

Table: events(id, user_id int, ts timestamptz, status text, payload jsonb)। Workload: (A) WHERE user_id=? AND ts DESC dashboard, (B) nightly WHERE status='pending', (C) ঘন INSERT batch। কোন index বানাবেন, কোনটা নয়?

ডিজাইন

(A) (user_id, ts DESC) — দুই শর্ত এক index-এ; LIMIT থাকলে chain-top থেকেই শেষ। (B) partial index ... WHERE status = 'pending' — ছোট, খাজনা শুধু matching row-দের। (C) list নূন্যতম — প্রতি index খাজনা; payload-এ GIN তখনই, containment query প্রমাণ হলে।

এরপর কী

প্রতিটা INSERT প্রতি index-এ random leaf-write — telemetry-জগতের সেকেন্ডে-লাখ-event-এ অসহ্য। জয়ী অন্য দর্শন: LSM-tree — সব write আগে memory-তে, তারপর immutable sorted file, background-এ merge। পরের লেসনে:

Memtable → SSTable pipeline — random write কীভাবে sequential হয়
Compaction-এর দুই school: size-tiered বনাম leveled (RocksDB/Cassandra)
Write/read/space amplification-র ত্রিভুজ; bloom filter-এ miss-আটকানো
আর Postgres কেন LSM নেয়নি — hash-tables-সুদসহ সেই রহস্যও

Amortized-analysis-র O(1) এবার production-decision।

B+ Tree Index — database index-এর কারখানা

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

B+ tree — ঝালিয়ে নেওয়া দুই সিদ্ধান্ত

Index = আলাদা এক relation

nbtree-র page anatomy

Index scan-এর পুরো পথ

Covering index — INCLUDE clause

Index-only scan — visibility map-এর গোপন

Write amplification — প্রতি INSERT-এর খাজনা

Delete ও bloat

Composite index — leftmost prefix rule

ভেতরে কী ঘটছে

pageinspect দিয়ে nbtree খোলা

উদাহরণ

একটা query-র পুরো journey

ছবিতে

নিজে চালিয়ে দেখুন

CREATE INDEX-এর স্কেল, তিন scan-plan-এর buffer-বিল, আর unused-index শিকার

নিজে বানান

DiskSimulatedBPlusTree — bytearray-'disk'-এ fixed 256-byte node, split/borrow/merge সহ

বাস্তব সিস্টেমে

Production-এ nbtree

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

B+ tree — ঝালিয়ে নেওয়া দুই সিদ্ধান্ত

Index = আলাদা এক relation

nbtree-র page anatomy

Index scan-এর পুরো পথ

Covering index — INCLUDE clause

Index-only scan — visibility map-এর গোপন

Write amplification — প্রতি INSERT-এর খাজনা

Delete ও bloat

Composite index — leftmost prefix rule

⚙ভেতরে কী ঘটছেUnder the hood

pageinspect দিয়ে nbtree খোলা

▶উদাহরণExample

একটা query-র পুরো journey

◫ছবিতেDiagram

⌘নিজে চালিয়ে দেখুনExperiment

CREATE INDEX-এর স্কেল, তিন scan-plan-এর buffer-বিল, আর unused-index শিকার

⚒নিজে বানানBuild it yourself

DiskSimulatedBPlusTree — bytearray-'disk'-এ fixed 256-byte node, split/borrow/merge সহ

◉বাস্তব সিস্টেমেReal-world usage

Production-এ nbtree

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

এরপর কী

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

ছবিতে

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী