ডেটাবেস ইনডেক্সিং ও কোয়েরি অপ্টিমাইজেশন
এই পাঠে যা শিখবেন
- ইনডেক্স ছাড়া কোয়েরির খরচ কেন $O(n)$ (ফুল টেবিল স্ক্যান)
- B-tree ইনডেক্স কীভাবে লুকআপকে $O(\log n)$-এ নামিয়ে আনে
- ইনডেক্সিং-এর লুকানো খরচ — রাইট স্পিড ও স্টোরেজ
- Python দিয়ে লিনিয়ার সার্চ বনাম বাইনারি সার্চের তুলনা — ১ লক্ষ রেকর্ডে তুলনা সংখ্যা গুনে
১ · ইনডেক্স ছাড়া — ফুল টেবিল স্ক্যান
একটি টেবিলে যদি কোনো ইনডেক্সIndexএকটি সহায়ক ডেটা স্ট্রাকচার (সাধারণত B-tree) যা একটি নির্দিষ্ট কলামের মান দিয়ে দ্রুত সংশ্লিষ্ট রেকর্ড খুঁজে বের করতে সাহায্য করে — টেবিলের প্রতিটি সারি একবার একবার করে না পড়েই। না থাকে, তাহলে একটি নির্দিষ্ট মান খুঁজতে ডেটাবেসকে ফুল টেবিল স্ক্যানFull Table Scanটেবিলের প্রতিটি সারি একে একে পড়ে খুঁজে বের করা যে কোন সারিটি শর্ত পূরণ করে — কোনো ইনডেক্স না থাকলে ডেটাবেসের একমাত্র উপায়। করতে হয় — অর্থাৎ টেবিলের প্রতিটি সারি একে একে পড়তে হয়। এক লক্ষ সারির টেবিলে সবচেয়ে খারাপ ক্ষেত্রে (রেকর্ডটি একেবারে শেষে থাকলে, বা টেবিলে না থাকলে) সবগুলো সারিই পড়তে হতে পারে — DSA কোর্সের ভাষায় এটি $O(n)$।
২ · ইনডেক্সসহ — B-tree ও $O(\log n)$ লুকআপ
একটি ইনডেক্স একটি নির্দিষ্ট কলামের মানগুলোকে একটি সাজানো, ব্র্যাঞ্চিং স্ট্রাকচারে (সাধারণত B-tree, DBMS কোর্সে বিস্তারিত) সংরক্ষণ করে রাখে। এর ফলে একটি নির্দিষ্ট মান খোঁজার সময় ডেটাবেস প্রতিটি সারি না পড়ে, বাইনারি সার্চের মতো ধাপে ধাপে সার্চ স্পেস অর্ধেক করে ফেলতে পারে — জটিলতা $O(\log n)$-এ নেমে আসে।
১,০০,০০০ রেকর্ডে সর্বোচ্চ ১,০০,০০০ তুলনা লাগতে পারে — $O(n)$।
একই ১,০০,০০০ রেকর্ডে মাত্র ~১৭ তুলনায় খুঁজে পাওয়া যায় — $O(\log n)$।
প্রতিটি ইনডেক্স প্রতিটি লেখার (write) সাথে নিজেও আপডেট হতে হয় — বেশি ইনডেক্স মানে ধীর
INSERT/UPDATE।৩ · কোড দিয়ে প্রমাণ — লিনিয়ার সার্চ বনাম বাইনারি সার্চ
নিচে ১,০০,০০০ সাজানো রেকর্ডের একটি লিস্টে সবচেয়ে খারাপ ক্ষেত্রে (শেষ রেকর্ড খোঁজা) লিনিয়ার সার্চ ("ইনডেক্স ছাড়া") ও বাইনারি সার্চ ("B-tree ইনডেক্সসহ") কতগুলো তুলনা করে তা গুনে দেখানো হয়েছে — এটি সরাসরি DSA কোর্সের Big-O বিশ্লেষণের একটি বাস্তব প্রয়োগ।
n = 100_000
sorted_records = list(range(0, n * 10, 10)) # সাজানো "primary key" মান: 0, 10, 20, ...
target = sorted_records[-1] # সবচেয়ে খারাপ ক্ষেত্র — একেবারে শেষের রেকর্ড
def linear_search_count_comparisons(data, target):
comparisons = 0
for value in data:
comparisons += 1
if value == target:
return comparisons
return comparisons
def binary_search_count_comparisons(data, target):
comparisons = 0
lo, hi = 0, len(data) - 1
while lo <= hi:
comparisons += 1
mid = (lo + hi) // 2
if data[mid] == target:
return comparisons
elif data[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return comparisons
linear_comparisons = linear_search_count_comparisons(sorted_records, target)
binary_comparisons = binary_search_count_comparisons(sorted_records, target)
print(f"মোট রেকর্ড সংখ্যা: {n:,}")
print(f"লিনিয়ার সার্চ (ইনডেক্স ছাড়া, O(n)): {linear_comparisons:,} টি তুলনা")
print(f"বাইনারি সার্চ (B-tree ইনডেক্সসহ, O(log n)): {binary_comparisons} টি তুলনা")
print(f"পার্থক্য: প্রায় {linear_comparisons // binary_comparisons:,} গুণ কম তুলনা লেগেছে")৪ · ইনডেক্সিং-এর লুকানো খরচ
ইনডেক্স বিনামূল্যে আসে না। প্রতিটি ইনডেক্স নিজে একটি আলাদা ডেটা স্ট্রাকচার, যা ডিস্কে জায়গা নেয় এবং প্রতিটি
INSERT/UPDATE/DELETE-এর সাথে সাথে নিজেও আপডেট হতে হয়। একটি টেবিলে যত
বেশি ইনডেক্স, রাইট অপারেশন তত ধীর হয়ে যায়। তাই ইঞ্জিনিয়াররা শুধু সেসব কলামেই ইনডেক্স তৈরি করেন যেগুলো
WHERE, JOIN, বা ORDER BY-তে ঘন ঘন ব্যবহৃত হয় — "সব কলামে ইনডেক্স দিন"
একটি সাধারণ ভুল যা রিড স্পিডের জন্য রাইট স্পিড ও স্টোরেজ বলি দেয়, প্রায়ই অপ্রয়োজনীয়ভাবে।
ইনডেক্স হলো read স্পিডের জন্য write স্পিড ও স্টোরেজের একটি সচেতন ট্রেড-অফ। রিড-হেভি সিস্টেমে (উচ্চ read:write অনুপাত, L02-তে দেখেছি) আক্রমণাত্মকভাবে ইনডেক্স করা লাভজনক; রাইট-হেভি সিস্টেমে প্রতিটি অতিরিক্ত ইনডেক্স সতর্কতার সাথে যোগ করা উচিত।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ একটি টেবিলের প্রতিটি কলামে ইনডেক্স তৈরি করলে সব কোয়েরিই কি দ্রুততর হবে?
রিড কোয়েরি হয়তো দ্রুততর হবে, কিন্তু এর একটি বড় মূল্য আছে — প্রতিটি INSERT/UPDATE/
DELETE-কে এখন প্রতিটি ইনডেক্সও আপডেট করতে হবে, ফলে রাইট অপারেশন উল্লেখযোগ্যভাবে ধীর হয়ে যায় এবং
ডিস্কে অতিরিক্ত স্টোরেজ লাগে। বাস্তবে শুধু সেসব কলামে ইনডেক্স করা উচিত যেগুলো আসলেই ঘন ঘন
WHERE/JOIN/ORDER BY-তে ব্যবহৃত হয়।
প্র ০২ বাইনারি সার্চের জন্য ডেটা সাজানো (sorted) থাকা দরকার — একটি B-tree ইনডেক্স কীভাবে এই "সাজানো" থাকার শর্ত পূরণ করে, যেখানে টেবিলে নতুন সারি যেকোনো সময় যোগ হতে পারে?
B-tree নিজেই একটি স্ব-ব্যালান্সিং ট্রি স্ট্রাকচার যা নতুন এন্ট্রি যোগ হওয়ার সাথে সাথে নিজের ভেতরের অর্ডার বজায় রাখে (DBMS কোর্সে বিস্তারিত) — এটি আসলে একটি বড় সাজানো লিস্ট রিবিল্ড করার বদলে, নতুন এন্ট্রি সঠিক জায়গায় দক্ষভাবে ঢুকিয়ে নেয়, যাতে ট্রি সবসময় সাজানো ও ব্যালান্সড থাকে এবং $O(\log n)$ লুকআপ বজায় থাকে।
প্র ০৩ একটি অ্যানালিটিক্স টেবিলে যেখানে দিনে একবার বাল্ক ইনসার্ট হয় কিন্তু সারাদিন হাজার হাজার রিড কোয়েরি চলে, সেখানে বেশি ইনডেক্স রাখা কি ঠিক সিদ্ধান্ত?
হ্যাঁ, এখানে বেশি ইনডেক্স রাখা যুক্তিসঙ্গত — কারণ read:write অনুপাত অত্যন্ত উঁচু (দিনে একবার রাইট, কিন্তু অসংখ্য রিড)। ইনডেক্সের রাইট-স্পিড খরচ দিনে একবার মাত্র প্রযোজ্য, কিন্তু রিড-স্পিড সুবিধা প্রতিটি কোয়েরিতে পাওয়া যায় — এটাই সেই বিরল ক্ষেত্র যেখানে আক্রমণাত্মক ইনডেক্সিং প্রায় বিনামূল্যে লাভজনক।
অনুশীলন
-
হিসাব করুন: $2^{20} = 1{,}048{,}576$। একটি টেবিলে ১০ লক্ষ (1,000,000) রেকর্ড থাকলে বাইনারি সার্চে (B-tree ইনডেক্সসহ) সবচেয়ে খারাপ ক্ষেত্রে আনুমানিক কতটি তুলনা লাগবে?
আনুমানিক ২০টি তুলনা — কারণ $2^{20} \approx 1{,}048{,}576$ যা ১০ লক্ষের চেয়ে বড়, তাই $\lceil \log_2(1{,}000{,}000) \rceil = 20$। তুলনা করুন — লিনিয়ার সার্চে একই টেবিলে সবচেয়ে খারাপ ক্ষেত্রে পুরো ১০ লক্ষ তুলনা লাগতে পারত।
-
কোড পরিবর্তন করুন: উপরের কোড সেলে
target-কেsorted_records[0](একেবারে প্রথম রেকর্ড) করে দিন এবংlinear_comparisons-এর মান কেমন বদলায় দেখুন, তারপরbinary_comparisons-এর মান কেমন বদলায় দেখুন।linear_comparisonsএখন ১ হয়ে যাবে (প্রথম রেকর্ডেই মিলে যাবে — লিনিয়ার সার্চের সেরা ক্ষেত্র)। কিন্তুbinary_comparisonsপ্রায় একই থাকবে (~১৭), কারণ বাইনারি সার্চ সবসময় মাঝখান থেকে শুরু করে — টার্গেটের অবস্থান নির্বিশেষে জটিলতা $O(\log n)$-ই থাকে। এটাই দেখায় কেন ইনডেক্স গড়পড়তা ও সবচেয়ে খারাপ ক্ষেত্রে নির্ভরযোগ্যভাবে দ্রুত, শুধু "ভাগ্য ভালো থাকলে" নয়।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫১টি পাঠ পরবর্তী পাঠ — রেপ্লিকেশন (Master-Slave ও Multi-Master) — শীঘ্রই যুক্ত হবে।
- L14 · SQL বনাম NoSQL আগের পাঠ ইনডেক্সিং SQL ও NoSQL উভয় ধরনের ডেটাবেসেই কীভাবে প্রযোজ্য তা বুঝতে আগের পাঠটি দেখুন।
- Data Structures & Algorithms কোর্স পূর্বশর্ত Big-O, বাইনারি সার্চ ও ট্রি স্ট্রাকচারের ভিত্তি জানতে DSA কোর্সটি দেখুন।
- সব Courses দেখুন ABCL TECH C, C++, Python, Java, JavaScript, DSA, DBMS, Discrete Mathematics ও System Design — সব এক জায়গায়।