B-Tree কীভাবে কাজ করে: Binary Tree থেকে Database Index পর্যন্ত

Database index বলতে প্রায় সবসময় একটা জিনিসই বোঝায়: B-Tree। PostgreSQL-এ CREATE INDEX লিখলে default-ভাবে B-Tree তৈরি হয়, MySQL-এর InnoDB-ও B-Tree ব্যবহার করে। কিন্তু B-Tree আসলে কী, আর database-এর জন্য এটা কেন এত ভালো, সেটা অনেক সময় অস্পষ্ট থাকে।

এই লেখায় আমরা একদম গোড়া থেকে শুরু করব: একটা node-এ একাধিক key কেন রাখা হয়, tree কীভাবে নিজেকে balanced রাখে, আর শেষে দেখব PostgreSQL-এর index page-এর সাথে এর সম্পর্ক কোথায়। PostgreSQL B-Tree index ব্যবহার করে কীভাবে query চালায় (Index Scan, Bitmap Scan ইত্যাদি), সেটা আছে PostgreSQL Internals সিরিজের Part 3-এ। এখানে শুধু data structure-টা।

Binary tree থেকে m-way tree

সাধারণ binary search tree-তে একটা node-এ একটা key থাকে আর সর্বোচ্চ দুটো child:

        20
       /  \
     10    30

ছোট value বাঁয়ে, বড় value ডানে। Search করতে প্রতিটা node-এ একটা comparison করে একদিকে নামতে হয়।

m-way tree-তে একটা node-এ একাধিক key থাকতে পারে, আর তাই অনেকগুলো child:

          [ 20 | 40 | 60 ]
          /    |    |    \
       <20  20–40 40–60  >60

এখানে key-গুলো (20, 40, 60) পুরো value space-কে কয়েকটা range-এ ভাগ করে দিয়েছে। প্রতিটা child একটা range-এর দায়িত্বে।

ধরা যাক আমরা 55 খুঁজছি:

55 > 40
55 < 60
→ 40–60 child-এ নামো

B-Tree-এর মূল idea এটাই: node-এর key-গুলোর সাথে compare করে ঠিক range-এর child-এ নেমে যাওয়া। B-Tree হলো এমন একটা m-way search tree, যেটা নিজেকে সবসময় balanced রাখে। Balanced মানে কী, সেটা একটু পরে দেখব।

n টা key কেন n+1 টা child বানায়

এটা মুখস্থ করার নিয়ম না, এটা নিজে থেকেই বের হয়ে আসে। প্রতিটা key একটা divider, যেটা একটা range-কে দুই ভাগ করে।

একটা key:

       [ 40 ]
      /      \
   <40        >40

1 key → 2 range

দুটো key:

      [ 20 | 40 ]
     /     |     \
  <20    20–40    >40

2 key → 3 range

তিনটা key:

     [ 20 | 40 | 60 ]
    /    |     |    \
 <20  20–40  40–60  >60

3 key → 4 range

Pattern পরিষ্কার:

children = keys + 1

একটা লাইনে n টা দাগ টানলে লাইনটা n+1 টুকরো হয়। Key ঠিক সেই দাগ।

Order `m`

B-Tree-এর order m মানে (এই লেখার definition অনুযায়ী) একটা node-এর সর্বোচ্চ m টা child থাকতে পারে। আর m টা child বানাতে m-1 টা divider লাগে, তাই:

order m = 5

max children = 5
max keys     = 4

        [ 20 | 40 | 60 | 80 ]
       /    |    |    |     \
    <20  20–40 40–60 60–80  >80

m-1 কোনো আলাদা rule না, এটা "n key → n+1 child" থেকেই আসে।

B-Tree শুধু number-এর জন্য না

উদাহরণে number ব্যবহার করা হয় কারণ সেটা সহজ। কিন্তু B-Tree-এর আসল শর্ত একটাই: key-গুলোকে একটা consistent নিয়মে ছোট থেকে বড় সাজানো যেতে হবে।

String-এর ক্ষেত্রে:

     [ "Cat" | "Mango" | "Tiger" ]
     /       |         |        \
 <Cat   Cat–Mango  Mango–Tiger  >Tiger

"Orange" > "Mango", "Orange" < "Tiger"
→ Mango–Tiger child

Date, timestamp, UUID, সবকিছুই একইভাবে কাজ করে, কারণ সবগুলোর একটা ordering আছে।

PostgreSQL কীভাবে জানে 'Apple' < 'Mango'? B-Tree নিজে কোনো type চেনে না। প্রতিটা data type-এর জন্য PostgreSQL-এ একটা operator class থাকে, যেটা বলে দেয় সেই type-এর দুটো value কীভাবে compare করতে হয়। Text-এর ক্ষেত্রে collation-ও ভূমিকা রাখে, অর্থাৎ কোন ভাষার sorting নিয়ম মেনে compare হবে।

     B-Tree: "এই দুটো key compare করো"
                    │
                    ▼
     operator class (type অনুযায়ী)
          │                 │
         INT               TEXT
       10 < 20      'Apple' < 'Mango'  (collation মেনে)

একটা index-এর একটা column-এ সব value একই type-এর, তাই [ 20 | 'Mango' | 60 ] জাতীয় mixed key কখনো তৈরি হয় না।

Multi-column index হলে প্রতিটা key আসলে একটা tuple:

CREATE INDEX idx_users_age_name ON users (age, name);

(20, 'Arif')
(20, 'Mukles')
(21, 'Sohail')
(25, 'Abir')

আগে age compare হয়। age সমান হলে তবেই name। প্রতিটা column নিজের type-এর নিয়মে compare হয়, তাই এক index-এ আলাদা type-এর column থাকতে কোনো সমস্যা নেই।

Self-balancing: tree কখনো একদিকে লম্বা হয় না

সাধারণ binary search tree-এর একটা বড় দুর্বলতা আছে। Sorted order-এ value insert করলে কী হয় দেখা যাক:

insert: 10, 20, 30, 40, 50

10
  \
   20
     \
      30
        \
         40
           \
            50

দেখতে tree, কিন্তু আসলে এটা একটা linked list। 50 খুঁজতে সবগুলো node পার হতে হয়। Database-এ id সাধারণত বাড়তেই থাকে, তাই এই worst case-টাই সবচেয়ে স্বাভাবিক case।

B-Tree এটা হতে দেয় না। এর সবচেয়ে গুরুত্বপূর্ণ guarantee:

সব leaf node সবসময় একই depth-এ থাকে।

                 [40]
               /      \
          [20]          [60]
         /    \        /    \
       [10]  [30]    [50]  [70]

root থেকে যেকোনো leaf: একই সংখ্যক ধাপ ✅

এর মানে root থেকে যেকোনো value খুঁজতে একই সংখ্যক node পার হতে হয়। একদিকে 2 ধাপ আর অন্যদিকে 20 ধাপ, এমন হয় না।

B-Tree কীভাবে এই guarantee রাখে?

Trick-টা হলো B-Tree নিচের দিকে না, উপরের দিকে বাড়ে।

নতুন key সবসময় সঠিক leaf-এ insert হয়।
Leaf ভরে গেলে (key সংখ্যা m-1 ছাড়িয়ে গেলে) সেটা দুই ভাগ হয় (split), আর মাঝের key-টা parent-এ উঠে যায়।
Parent-ও ভরে গেলে সেটাও split হয়, এভাবে উপরে উঠতে থাকে।
Root split হলে নতুন একটা root তৈরি হয়। শুধু তখনই tree-এর height এক বাড়ে, আর সেটা সব leaf-এর জন্য একসাথে।

order 4 (max 3 key), leaf ভরা: [10 | 20 | 30]
insert 40:

  [10 | 20 | 30 | 40]   ← overflow
          ↓ split, মাঝের key উপরে
        [ 30 ]
       /      \
  [10 | 20]  [30 | 40]   (B+ Tree-তে 30 leaf-এও থাকে)

যেহেতু নতুন level সবসময় উপরে যোগ হয়, কোনো leaf অন্যদের থেকে নিচে নেমে যেতে পারে না। Delete-এর সময় উল্টো কাজ হয়: node খুব খালি হলে পাশের node থেকে key ধার নেয় বা merge করে।

এই কারণে B-Tree-তে root ছাড়া প্রতিটা node-কে অন্তত অর্ধেক ভরা থাকতে হয় (order m হলে অন্তত ⌈m/2⌉ টা child)। এতে tree অপ্রয়োজনীয়ভাবে লম্বা আর ফাঁকা হয়ে যায় না।

Insert-এর পুরো সিদ্ধান্ত এক নজরে:

flowchart TD
  K(["নতুন key"]) --> L["সঠিক leaf খুঁজে বের করো"]
  L --> F{"Leaf-এ জায়গা আছে?"}
  F -->|হ্যাঁ| D(["Sorted জায়গায় বসাও — শেষ"])
  F -->|না| SP["Leaf split<br/>মাঝের key parent-এ পাঠাও"]
  SP --> PF{"Parent-এ জায়গা আছে?"}
  PF -->|হ্যাঁ| D2(["শেষ"])
  PF -->|না| UP["Parent-ও split,<br/>আরও উপরে ওঠো"]
  UP --> RT{"Root split হলো?"}
  RT -->|না| PF
  RT -->|হ্যাঁ| NR(["নতুন root — height এক বাড়ে,<br/>সব leaf-এর জন্য একসাথে"])

Database-এর জন্য B-Tree কেন এত ভালো

এখন আসল প্রশ্ন। Balanced binary tree-ও তো balanced থাকে। তাহলে database B-Tree কেন বেছে নেয়?

উত্তর: disk একবারে একটা পুরো page পড়ে। PostgreSQL-এর page ৮ KB। একটা node পড়া মানে একটা page পড়া, আর page RAM-এ না থাকলে সেটা disk থেকে আনতে হয়, যেটা ধীর। তাই লক্ষ্য হলো যত কম node (page) পড়ে value খুঁজে পাওয়া যায়।

`m` ঠিক হয় page size থেকে

B-Tree-এর একটা node = একটা disk page। Page-এ যত বেশি key আর child pointer ধরে, m তত বড়।

ধরা যাক page-এ ব্যবহারযোগ্য জায়গা 8000 bytes

entry প্রতি 100 bytes → ~80 child
entry প্রতি 16 bytes  → ~500 child

ছোট key (যেমন integer) মানে এক page-এ শত শত child। এটাকে বলে fan-out বা branching factor।

Height-এর হিসাব

১০ লাখ (1,000,000) row-এর একটা index ধরা যাক।

Binary tree (fan-out 2):

level 1 → 2
level 2 → 4
level 3 → 8
...
level 20 → ~1,000,000

≈ 20 level → সবচেয়ে খারাপ ক্ষেত্রে 20 টা page read

B-Tree (ধরা যাক fan-out 100):

level 0 →         1 page
level 1 →       100 page
level 2 →    10,000 page
level 3 → 1,000,000 entry

≈ 3–4 level → 3–4 টা page read

কোটি row হলেও B-Tree-তে মাত্র এক level বাড়ে। আর root ও উপরের কয়েকটা level প্রায় সবসময় RAM-এ (PostgreSQL-এর shared buffers-এ) cached থাকে, তাই বাস্তবে disk থেকে পড়তে হয় হয়তো এক-দুটো page।

B-Tree হলো wide কিন্তু shallow। কম height মানে কম page read, কম I/O, দ্রুত lookup।

Binary tree: সরু আর গভীর        B-Tree: চওড়া আর অগভীর

      O                                O
     / \                     / / / / / | \ \ \ \ \
    O   O                    O O O O O O O O O O O
   /     \
  O       O
 /
O

B+ Tree: database আসলে যেটা ব্যবহার করে

Textbook B-Tree-তে internal node-এর key-এর সাথেও data (বা data-র pointer) থাকতে পারে। Database-এ সাধারণত একটা variant ব্যবহার হয়: B+ Tree। পার্থক্য দুটো:

১. Internal node শুধু পথ দেখায়। আসল entry (key + row-এর ঠিকানা) সব থাকে leaf-এ। Internal node-এ data না থাকায় সেখানে আরও বেশি key ধরে, fan-out আরও বাড়ে।

২. Leaf-গুলো একে অপরের সাথে linked।

                 [ 30 | 60 ]
                /     |     \
        [10, 20] ⇄ [30, 40, 50] ⇄ [60, 70, 80]

দ্বিতীয়টা range query-কে খুব দ্রুত করে:

SELECT * FROM users WHERE age BETWEEN 30 AND 70;

1. root থেকে নেমে 30-এর leaf খুঁজে বের করো   (কয়েকটা page)
2. তারপর leaf ধরে পাশে পাশে হাঁটো:
   30 → 40 → 50 → 60 → 70
   প্রতিটা value-এর জন্য আবার root থেকে শুরু করতে হয় না

একই কারণে ORDER BY age index থেকে সরাসরি sorted order-এ পড়া যায়, আলাদা sort লাগে না।

B+ Tree-এর গঠন আর range scan-এর পথ:

flowchart TD
  ROOT["Root: 30 | 60"] --> L1["Leaf: 10, 20"]
  ROOT --> L2["Leaf: 30, 40, 50"]
  ROOT --> L3["Leaf: 60, 70, 80"]
  L1 <-->|link| L2
  L2 <-->|link| L3
  Q(["BETWEEN 30 AND 70"]) -.->|"একবার নেমে 30 খোঁজো"| L2
  L2 -.->|"পাশের leaf ধরে চলো"| L3

PostgreSQL-এর btree

PostgreSQL-এর B-Tree index textbook B+ Tree-এর হুবহু কপি না, তবে মূল বৈশিষ্ট্যগুলো একই: internal page পথ দেখায়, leaf page-এ index entry থাকে, আর একই level-এর page-গুলো পাশের page-এর সাথে linked। এটা Lehman–Yao নামের একটা high-concurrency B-Tree design-এর ওপর তৈরি, যাতে অনেক transaction একসাথে index পড়তে ও লিখতে পারে।

আর একটা গুরুত্বপূর্ণ কথা: index-এর leaf-এ পুরো row থাকে না। থাকে key আর row-টা heap-এর কোথায় আছে তার ঠিকানা, অর্থাৎ TID (block number, item number)।

B-Tree root page
      ↓
internal page
      ↓
leaf page:  key = 847293 → TID (5021, 7)
      ↓
heap page 5021, item 7 → আসল row

Heap, page আর TID কী, সেটা বিস্তারিত আছে PostgreSQL Internals Part 1-এ।

পুরো ছবি একসাথে

B-Tree
 ├─ m-way search tree: এক node-এ অনেক key
 ├─ n key → n+1 child (key = range divider)
 ├─ order m → max m child, max m-1 key
 ├─ যেকোনো sortable type (operator class, collation)
 ├─ সব leaf একই level-এ; split করে উপরের দিকে বাড়ে
 ├─ node = disk page → বড় fan-out → ছোট height → কম I/O
 └─ B+ Tree: data শুধু leaf-এ, leaf-গুলো linked → দ্রুত range scan

নিজেকে যাচাই করো

১. Order m = 6 এমন একটা B-Tree-এর node-এ সর্বোচ্চ কয়টা key থাকতে পারে?

২. Binary search tree-তে sorted order-এ insert করলে tree linked list হয়ে যায়। B-Tree-তে কেন এটা হয় না?

৩. WHERE age BETWEEN 30 AND 70 query-তে B+ Tree-এর কোন বৈশিষ্ট্য সবচেয়ে বেশি সাহায্য করে?

উত্তর: (১) ৫টা, কারণ ৬টা child বানাতে ৫টা divider লাগে। (২) B-Tree নতুন key leaf-এ বসায় আর ভরে গেলে split করে মাঝের key উপরে পাঠায়; height শুধু root split হলে বাড়ে, সব leaf-এর জন্য একসাথে, তাই সব leaf সবসময় একই depth-এ থাকে। (৩) Leaf-গুলো linked থাকা: একবার 30-এর leaf খুঁজে পেলে বাকিটা পাশের leaf ধরে পড়ে ফেলা যায়, বারবার root থেকে নামতে হয় না।

B-Tree বুঝে ফেললে PostgreSQL কীভাবে এই tree ব্যবহার করে Index Scan, Index Only Scan বা Bitmap Scan চালায়, সেটা অনেক সহজ লাগবে। সেটা আছে PostgreSQL Internals Part 3: Index কীভাবে কাজ করে-এ।