B-Trees & Indexes

গল্পে বুঝি

আল-খোয়ারিজমি প্রথমবার শহরের বিশাল সেন্ট্রাল লাইব্রেরিতে গেল একটা বই খুঁজতে। ভেতরে ঢুকে সে থমকে গেল — লাখ লাখ বই, সারি সারি তাক, চোখ যত দূর যায় শুধু বই। এক তাক থেকে আরেক তাক ঘুরে ঘুরে খুঁজলে তো সারা জীবন লেগে যাবে। কিন্তু দরজার পাশেই দাঁড়ানো ফাতিমা আল-ফিহরি, লাইব্রেরিয়ান, হেসে বললেন — “একটাও তাক না ঘেঁটেই বের করে দিচ্ছি।” প্রথমে তিনি একটা বড় ড্রয়ার টেনে বিষয় বেছে নিলেন — ইতিহাস। সেই ড্রয়ারের ভেতরের ডিভাইডার ধরে বেছে নিলেন ঠিক তাকটা। আর সেই তাকের ছোট ট্যাব ধরে আঙুল রাখলেন একদম বইটার গায়ে।

তিনটা ছোট ছোট ধাপ — বিষয়, তারপর তাক, তারপর বই। লাখ লাখ বইয়ের একটাও না ছুঁয়ে, শুধু তিনবার পরিসর ছোট করে আল-খোয়ারিজমির বইটা হাতে চলে এল। প্রতিটা ধাপে সম্ভাবনার পরিসর অর্ধেকের চেয়েও অনেক বেশি কমে যাচ্ছিল, তাই বই যত বাড়ুক, ধাপ প্রায় একই তিন-চারটাই থাকে।

এই ব্যাপারটাই ঠিক B-tree index। লাইব্রেরির নেস্টেড ক্যাটালগ হলো multi-level balanced index — বিষয়ের ড্রয়ার, তাকের ডিভাইডার, বইয়ের ট্যাব হলো tree-র একেকটা level-এর node। পুরো লাইব্রেরি scan না করে মাত্র কয়েকটা level নিচে নেমে ঠিক জায়গায় পৌঁছানোটাই few-level descent, আর তাই বই লাখ হোক বা কোটি, lookup থাকে O(log n) — ধাপ সামান্যই বাড়ে। বাস্তবে database-এর index ঠিক এভাবেই কাজ করে: কোটি row-এর টেবিলেও পুরো টেবিল scan না করে B-tree-র কয়েকটা level নেমে সেকেন্ডের ভগ্নাংশে সঠিক row খুঁজে দেয়।

B-Trees কেন?

B-tree হলো একটা self-balancing tree যা disk access-এর জন্য অপটিমাইজড। Binary tree-র (প্রতি node-এ 2টা child) মতো নয়, B-tree-র প্রতি node-এ শত শত child থাকে — প্রতিটা node একটা disk page ভরে ফেলে। এর মানে হলো লক্ষ লক্ষ entry থাকা একটা tree মাত্র 3-4 level গভীর।

3 level = লক্ষ লক্ষের মধ্যে যেকোনো row খুঁজে পেতে 3 disk read।

B-Tree Structure

interface BTreeNode {
	keys: number[]; // sorted keys
	values: (Row | number)[]; // row data (leaf) or child page IDs (internal)
	isLeaf: boolean;
	// In a node with N keys, there are N+1 children
	// keys:     [10,    20,    30]
	// children: [<10] [10-20] [20-30] [>30]
}

class BTree {
	private root: BTreeNode;
	private order: number; // max keys per node (typically 100-500)

	search(key: number): Row | null {
		let node = this.root;

		while (!node.isLeaf) {
			// Binary search within the node (in-memory, fast)
			const idx = this.findChildIndex(node, key);
			node = this.readPage(node.values[idx] as number);
			// Each iteration = 1 disk read
		}

		// At leaf — find the key
		const idx = node.keys.indexOf(key);
		return idx >= 0 ? (node.values[idx] as Row) : null;
	}

	private findChildIndex(node: BTreeNode, key: number): number {
		// Binary search: O(log N) within node, but N is small (~200)
		let lo = 0,
			hi = node.keys.length;
		while (lo < hi) {
			const mid = (lo + hi) >> 1;
			if (node.keys[mid] <= key) lo = mid + 1;
			else hi = mid;
		}
		return lo;
	}
}

বাস্তবে Index কীভাবে কাজ করে

-- Without index: full table scan (reads EVERY page)
SELECT * FROM users WHERE email = 'fatima@example.com';
-- Reads: ~10,000 pages for a 1M row table

-- With index: B-tree lookup (reads 3-4 pages)
CREATE INDEX idx_users_email ON users (email);
SELECT * FROM users WHERE email = 'fatima@example.com';
-- Reads: 3 pages (B-tree traversal) + 1 page (heap fetch)

Composite Index

-- Composite index: ordered by (country, city, name)
CREATE INDEX idx_location ON users (country, city, name);

-- Uses the index (leftmost prefix match):
SELECT * FROM users WHERE country = 'US';                        -- ✓
SELECT * FROM users WHERE country = 'US' AND city = 'NYC';      -- ✓
SELECT * FROM users WHERE country = 'US' AND city = 'NYC' AND name = 'Fatima'; -- ✓

-- Cannot use the index:
SELECT * FROM users WHERE city = 'NYC';              -- ✗ (skips country)
SELECT * FROM users WHERE name = 'Fatima';            -- ✗ (skips country, city)

B-Tree Insertion আর Split

যখন একটা node পূর্ণ হয়ে যায়, তখন এটা দুইটা node-এ split হয় আর মাঝের key-টা parent-এর দিকে push করে দেয়:

insert(key: number, value: Row): void {
  const leaf = this.findLeaf(key);

  if (leaf.keys.length < this.order) {
    // Space available — insert directly
    this.insertIntoNode(leaf, key, value);
  } else {
    // Node full — split
    const [leftNode, rightNode, medianKey] = this.splitNode(leaf, key, value);
    // Push medianKey up to parent
    // Parent might also split → cascades up
    this.insertIntoParent(leaf.parent, medianKey, leftNode, rightNode);
  }
}

এই কারণেই B-tree balanced থাকে — split উপরের দিকে propagate হয়, আর tree শুধু root-এ গিয়ে উঁচু হয়।

Index-এর ধরন

Type	কীভাবে কাজ করে	সবচেয়ে ভালো যার জন্য
B-tree	Sorted tree, range queries	=, <, >, BETWEEN, ORDER BY
Hash	Hash table lookup	শুধু = (range নয়)
GIN	Inverted index	Full-text search, arrays, JSONB
GiST	Generalized search tree	Geometry, nearest-neighbor
BRIN	Block range index	বড়, স্বাভাবিকভাবে ordered টেবিল

Index-এর খরচ

Index read দ্রুত করে কিন্তু write ধীর করে দেয়:

// Every INSERT/UPDATE/DELETE must also update all indexes
// Table with 5 indexes:
// INSERT → 1 heap write + 5 index writes = 6 writes

// Index maintenance costs:
// - Write amplification: each data write triggers multiple index writes
// - Space: indexes can be larger than the table itself
// - Vacuum overhead (PostgreSQL): dead index entries need cleanup

মূল কথাগুলো

1. B-tree অগভীর — লক্ষ লক্ষ row থাকলেও 3-4 level গভীর, তাই lookup মাত্র 3-4 disk read
2. Composite index-এর ক্রম গুরুত্বপূর্ণ — query-কে leftmost prefix-এর সাথে মিলতে হবে
3. Index write speed-এর বিনিময়ে read speed দেয় — প্রতিটা অতিরিক্ত index write ধীর করে দেয়
4. সঠিক index type বেছে নিন — range-এর জন্য B-tree, equality-র জন্য hash, full-text-এর জন্য GIN