B-Tree Index কী?

B-Tree (Balanced Tree) হলো ডেটাবেজে সবচেয়ে বেশি ব্যবহৃত Index ডেটা স্ট্রাকচার। MySQL, PostgreSQL সহ প্রায় সব রিলেশনাল ডেটাবেজ ডিফল্টভাবে B-Tree Index ব্যবহার করে। এটি একটি Self-Balancing Tree যেখানে প্রতিটি নোড সর্টেড ক্রমে ডেটা ধারণ করে।

B-Tree-এর গঠন

                    [30 | 70]
                   /    |    \
           [10|20]   [40|50|60]   [80|90]
           /  |  \    /  |  |  \   /  |  \
         [5] [15] [25] [35][45][55][65][75][85][95]

মূল বৈশিষ্ট্য:

• প্রতিটি নোডে একাধিক Key থাকতে পারে
• সব Leaf Node একই Level-এ থাকে (Balanced)
• Root থেকে যেকোনো Leaf Node-এ পৌঁছাতে একই সংখ্যক Step লাগে
• ডেটা Sorted order-এ সংরক্ষিত থাকে

B-Tree Index কেন কার্যকর?

সময় জটিলতা (Time Complexity)

উদাহরণ: ১০ লক্ষ রেকর্ডের টেবিলে:

• Full Scan: ১,০০০,০০০ তুলনা
• B-Tree Index: মাত্র ~২০টি তুলনা (log₂ 1,000,000 ≈ 20)

B-Tree Index কোন Query-তে কাজ করে?

-- ✅ Equality Search — B-Tree দুর্দান্ত
SELECT * FROM employees WHERE id = 1001;

-- ✅ Range Search — B-Tree দুর্দান্ত
SELECT * FROM employees WHERE salary BETWEEN 50000 AND 80000;

-- ✅ Prefix Search — B-Tree কাজ করে
SELECT * FROM employees WHERE name LIKE 'Rah%';

-- ✅ Sorting — B-Tree সাহায্য করে (ইতিমধ্যে sorted)
SELECT * FROM employees ORDER BY name;

-- ✅ Greater/Less Than — B-Tree কাজ করে
SELECT * FROM employees WHERE age > 30;

-- ❌ Suffix/Middle Search — B-Tree কাজ করে না
SELECT * FROM employees WHERE name LIKE '%ahmed%';

-- ❌ Function-based — B-Tree কাজ করে না (সাধারণত)
SELECT * FROM employees WHERE YEAR(created_at) = 2024;

B-Tree Index তৈরি করা

MySQL-এ

-- সাধারণ B-Tree Index (ডিফল্ট)
CREATE INDEX idx_emp_salary ON employees(salary);

-- Unique B-Tree Index
CREATE UNIQUE INDEX idx_emp_email ON employees(email);

-- Composite B-Tree Index
CREATE INDEX idx_emp_dept_salary ON employees(department_id, salary);

-- Index তৈরির সময় স্পষ্টভাবে USING BTREE উল্লেখ
CREATE INDEX idx_emp_name ON employees(name) USING BTREE;

PostgreSQL-এ

-- PostgreSQL ডিফল্টভাবে B-Tree ব্যবহার করে
CREATE INDEX idx_emp_name ON employees(name);

-- স্পষ্টভাবে উল্লেখ
CREATE INDEX idx_emp_salary ON employees(salary) USING BTREE;

-- Descending Order Index
CREATE INDEX idx_emp_salary_desc ON employees(salary DESC);

Spring Boot JPA-তে B-Tree Index

import jakarta.persistence.*;

@Entity
@Table(
    name = "employees",
    indexes = {
        // এগুলো সবই ডিফল্টভাবে B-Tree Index হবে
        @Index(name = "idx_emp_email", columnList = "email", unique = true),
        @Index(name = "idx_emp_salary", columnList = "salary"),
        @Index(name = "idx_emp_dept_salary", columnList = "department_id, salary"),
        @Index(name = "idx_emp_name", columnList = "name")
    }
)
public class Employee {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    private String name;
    private String email;
    private Double salary;
    private Long departmentId;

    @Column(name = "created_at")
    private LocalDateTime createdAt;
}

B-Tree Index-এর কার্যপ্রণালী বিস্তারিত

Search প্রক্রিয়া

salary = 55000 খুঁজতে:

Root Node: [30000 | 70000]
    55000 > 30000 এবং 55000 < 70000 → মাঝের শাখায় যাও

Middle Node: [40000 | 50000 | 60000]
    55000 > 50000 এবং 55000 < 60000 → পরের শাখায় যাও

Leaf Node: [51000 | 53000 | 55000 | 57000]
    55000 পাওয়া গেছে! → Row pointer দিয়ে সরাসরি ডেটা পড়ো

Range Query

salary BETWEEN 45000 AND 60000:

B-Tree দিয়ে 45000 খোঁজো → Leaf Node-এ পৌঁছাও
তারপর Leaf Node-গুলো Sequential-ভাবে পড়ো যতক্ষণ 60000 পার না হয়
(Leaf Node-গুলো Linked List-এর মতো সংযুক্ত থাকে)

Composite B-Tree Index-এর কলাম ক্রম গুরুত্বপূর্ণ

-- Index: (department_id, salary)
CREATE INDEX idx_dept_salary ON employees(department_id, salary);

-- ✅ এই Index ব্যবহার করবে (leading column আছে)
WHERE department_id = 5
WHERE department_id = 5 AND salary > 50000
WHERE department_id = 5 ORDER BY salary

-- ❌ এই Index ব্যবহার করবে না (leading column নেই)
WHERE salary > 50000  -- শুধু salary দিয়ে

নিয়ম: Composite Index-এ সবচেয়ে বেশি ব্যবহৃত এবং High Cardinality কলামটি প্রথমে রাখুন।

EXPLAIN দিয়ে B-Tree Index যাচাই

EXPLAIN SELECT * FROM employees WHERE salary BETWEEN 50000 AND 80000;

-- Output:
-- type: range (ভালো — B-Tree range scan)
-- key: idx_emp_salary (Index ব্যবহার হচ্ছে)
-- rows: 1500 (আনুমানিক রেকর্ড সংখ্যা)
-- Extra: Using index condition

সংক্ষেপে

উপসংহার

B-Tree Index হলো ডেটাবেজ Performance অপ্টিমাইজেশনের সবচেয়ে মৌলিক ও শক্তিশালী টুল। এটি Equality, Range, Sorting সহ প্রায় সব ধরনের Query-তে কার্যকর। Spring Boot বা যেকোনো JPA অ্যাপ্লিকেশনে @Index annotation ব্যবহার করলে ডিফল্টভাবে B-Tree Index তৈরি হয়। Composite Index-এ কলামের সঠিক ক্রম নির্বাচন করা Performance-এর জন্য অত্যন্ত গুরুত্বপূর্ণ।