MySQL, PostgreSQL, MongoDB মূলত B+ ট্রি ব্যবহার করে তার কিছু কারণ রয়েছে,
প্রতিটি নোড একাধিক key-pointer সংরক্ষণ করতে পারে। এমনকি কোটি কোটি row এর জন্যও, একটি lookup সাধারণত মাত্র ২-৪টি page এক্সেস করলে expected data পেতে পারি।
Leaf Node গুলো sequentially সংযুক্ত থাকে, যা রেঞ্জ কোয়েরিকে (যেমন, WHERE age BETWEEN 20 AND 30) খুবই efficient করে তুলে।
[20, 35] ← internal (root)
/ | \
/ | \
[10, 15] [25, 30] [40, 45, 50] ← leaf nodes
root নোডগুলো শুধু কী (key) ও পয়েন্টার ধরে রাখে সার্চের দিকনির্দেশনার জন্য।
leaf নোডগুলোতে মূলত, আসল ডেটা বা রেকর্ডের রেফারেন্স থাকে।
প্রতিটি লিফ নোড একটি আরেকটির সাথে Linked List আকারে connected।
প্রথমে আমরা বুঝেনি এই ডাটাবেস ইনডেক্সিং কি?
এটি একটি টেকনিক, দ্রুত ডাটা রিট্রিভ করে আনার জন্য। আপনি এটিকে আপনার বইয়ের সূচীপত্রের সাথে তুলনা করতে পারেন, একটি করে সম্পূর্ণ পৃষ্ঠা দেখে সন্ধান করার পরিবর্তে, আপনি সূচিপত্র দেখে নির্দিষ্ট পৃষ্ঠা বের করে সরাসরি ঐ পৃষ্ঠায় চলে গেলেন। ডাটাবেস ইনডেক্সিং এরকম কাজ করে।
সাধারণত একটি নির্দিষ্ট কলামকে ইনডেক্সিং করে রাখতে পারি(আবার চাইলে একাধিক কলামকেও একসাথে কিংবা আলাদা আলাদা করেও ইনডেক্সিং করতে পারি)।
যদি আমরা ইনডেক্সিং করি তাহলে আমরা সরাসরি সেই প্রত্যাশিত(expected) row পেয়ে যাব। অন্যথায় একটি একটি করে সব row সার্চ করে, expected row বের করতে হবে।
রিলেশনাল ডেটাবেসের সাধারণ ইনডেক্স B+ Tree স্ট্রাকচারে সংরক্ষিত থাকে।
এখন কিছু গুরুত্বপূর্ণ ইনডেক্স বুঝে নেয়া যাক।
আমরা যখন MySQL (InnoDB ইঞ্জিন)-এ PRIMARY KEY উল্লেখ করি, তখন সেটি শুধু একটি ইউনিক ইনডেক্স তৈরি করে না, এটি পুরো টেবিলের জন্য Clustered Index হিসেবেও কাজ করে।
তখন Primary Key sequentially, B+ ট্রির লিফ নোডে সম্পূর্ণ row পাওয়া যায়। সেটাই হচ্ছে Cluster Index। উদাহরণ,
[103] <-- root
/ \
[101,102] [104,105] <-- leaf
B+ Tree Internal Node Leaf Node (actual data)
---------------------------------------------------------
[103].................. -> | 101 | Alice | London |
[103].................. -> | 102 | Bob | New York |
[103].................. -> | 103 | Charlie | Arizona |
[103].................. -> | 104 | David | Sydney |
[103].................. -> | 105 | Eve | Melbourne |
Leaf নোডে ঠিক এরকমভাবে ডাটা সুসজ্জিতভাবে থাকে। লিফ নোডে সকল ডাটা (sequentially) থাকার ফলে, আমরা সরাসরি সেই ডাটা দ্রুত এক্সেস করতে পারি।
PostgreSQL এ সরাসরি Cluster Index নেই। বরং তা Heap-based Storage Model ব্যবহার করে। তা আমরা অন্য কোনো অধ্যায়ে বিস্তারিত দেখবো।
এটি মূলত Primary Key এর বাইরে অন্য কোনো কলামে ইনডেক্স করলে সেটাই হচ্ছে Secondary index।
CREATE INDEX idx_user_name ON users(user_name);
লুকআপ প্রক্রিয়া (দুই ধাপে):
কী হয়: B+ Tree সেকেন্ডারি ইনডেক্সে সার্চ করা হয়, যেখানে নির্দিষ্ট সার্চ কলামের মান মেলানো হয়।
ধরা যাক, আপনি একটি টেবিলে user_name কলামের উপর Secondary Index তৈরি করেছেন, এবং সার্চ করছেন user_name = ‘lahin31’।
ধাপ ১: রুট থেকে শুরু:
রুট নোডে সার্চ শুরু হয়। এখানে থাকা key-গুলোর সাথে ‘lahin31’ তুলনা করা হয় এবং সঠিক পয়েন্টার বেছে নেওয়া হয় যা পরবর্তী নোডের দিকে নিয়ে যায়।
ধাপ ২: ইন্টারমিডিয়েট নোড:
ইন্টারমিডিয়েট নোডে গিয়ে আবার key-গুলোর সাথে তুলনা করা হয় এবং সঠিক node বেছে নেওয়া হয়। এভাবে সার্চ লিফ নোড পর্যন্ত পৌঁছায়।
ধাপ ৩: লিফ নোডে সার্চ:
লিফ নোডে পৌঁছে ‘lahin31’ নামের সাথে মিলে যাওয়া এন্ট্রি খুঁজে বের করা হয়। এখানে সেকেন্ডারি কী (‘lahin31’) এর পাশে সংশ্লিষ্ট প্রাইমারি কী (যেমন, ID = 101) পাওয়া যায়।
ফলাফল: এই ধাপে সংশ্লিষ্ট রেকর্ডের Primary Key পাওয়া যায়।
কী হয়: পাওয়া Primary Key ব্যবহার করে Clustered Index (যেখানে আসল ডেটা ফিজিক্যালি সাজানো থাকে) থেকে সম্পূর্ণ রেকর্ড (row) রিট্রিভ করা হয়।
ফলাফল: প্রত্যাশিত(expected) row পাওয়া যায়।
তার মানে দাঁড়ায়, Secondary Index-এ দুই ধাপের সার্চ হয়ে থাকে:
আপনি কোনো কলামে যখন UNIQUE constraint বলে দিবেন, তখন ডেটাবেস সেই কলামের উপর একটি Unique Index তৈরি করে। Unique Index কলামের প্রতিটি রো-তে uniqueness নিশ্চিত করে।
আপনি UNIQUE constraint একক কলামের জন্য ব্যবহার করতে পারেন, আবার একাধিক কলাম মিলিয়েও (group) ব্যবহার করতে পারেন।
এখানে কলামে ইনডেক্সিং থাকার ফলে Query দ্রুততর হয়ে থাকে।
মনে রাখবেন UNIQUE index দিলে সেটি Clustered হবে না; এটি সাধারণত Secondary Index।
(চলমান)