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।
আধুনিক ডাটাবেস ইঞ্জিনগুলোতে আপনি ইনডেক্সের মধ্যে নন-কি কলামগুলো সরাসরি যোগ করতে পারেন, যার ফলে ইনডেক্সটি কোয়েরির আরও বেশি প্রয়োজন মেটাতে পারে এবং টেবিলের মূল স্টোরেজ (হিপ) থেকে ডেটা আনার দরকার পড়ে না। এখন নিচের কোয়েরিটি বিবেচনা করুন:
SELECT title, genre FROM books WHERE genre = 'Science Fiction';
এখানে genre কলামে একটি সেকেন্ডারি ইনডেক্স আছে (InnoDB-তে)। কিন্তু title আনার জন্য ডাটাবেসকে তবু টেবিলের মূল স্টোরেজ (হিপ) থেকে ডেটা পড়তে হয়। এতে সময় লাগে।
কিন্তু যদি আপনি একটি কভারিং ইনডেক্স তৈরি করেন এভাবে:
CREATE INDEX idx_covering ON books (genre, title);
তাহলে একই query চালালে:
SELECT title, genre FROM books WHERE genre = 'Science Fiction';
MySQL বা অন্য যেকোনো ডাটাবেস সরাসরি index থেকেই প্রয়োজনীয় সব কলামের ডেটা পেয়ে যাবে, টেবিলের মূল স্টোরেজে যাওয়ার কোনো দরকার হবে না।
কিন্তু যদি কভারিং ইনডেক্স না থাকে এবং query এরকম হয়:
SELECT * FROM books WHERE genre = 'Science Fiction';
তাহলে ডাটাবেসকে সব কলাম আনার জন্য টেবিলের মূল স্টোরেজে যেতে হবে। এতে I/O অপারেশন বেড়ে যায় এবং পারফরম্যান্স কমে যায়।
একটি বিষয় আমাদেরকে মনে রাখতে হবে,
ইনডেক্সের কলাম অর্ডার (Column Order) খুব গুরুত্বপূর্ণ।
মানে, আপনার ইনডেক্স এরকম হলে, INDEX (genre, title)
এবং আপনার query যদি এরকম হয়,
SELECT title, genre FROM books WHERE genre = 'Science Fiction';
এটি ভালো কাজ করবে। আবার query এরকম হলে,
SELECT title, genre FROM books WHERE genre = 'Science Fiction' AND title = 'Software Engineering';
এটি ভালো কাজ করবে। কিন্তু query এরকম হলে,
SELECT title, genre FROM books WHERE title = 'Software Engineering';
তা ভালো কাজ করবে না। কারণ MySQL(innodb) index শুধুমাত্র তখনই কার্যকরভাবে ব্যবহার করতে পারে, যদি WHERE ক্লজে ব্যবহৃত কলামগুলো ইনডেক্সের leftmost columns ম্যাচ করে।
আমাদের মনে রাখতে হবে, কভারিং ইনডেক্স ভালো কাজ করে - Read-heavy system এ।
সাধারণত সকল প্রকারের ইনডেক্স আমাদের সিস্টেমের WRITE query latency বৃদ্ধি করে থাকে। কারণ তখন প্রতিটা entry এর সময় নতুন করে ইনডেক্স স্ট্রাকচার করা লাগে।