B-Tree و Clustered Index در InnoDB: ایندکس واقعاً چیست؟

چرا یک کوئری ۲ ثانیه و دیگری ۲ میلی‌ثانیه طول می‌کشد؟

بدون ایندکس، پیدا کردن سفارش‌های یک مشتری یعنی خواندن تک‌تک ردیف‌های جدول (full table scan). ایندکس یک ساختار مرتب جداگانه است که مثل فهرست الفبایی آخر کتاب، مستقیم به جای درست می‌برد. نوع پیش‌فرض ایندکس در InnoDB درخت B+Tree است.

ساختار B+Tree

• داده در صفحههای 16 کیلوبایتی ذخیره می‌شود. هر صفحه‌ی میانی صدها کلید و اشاره‌گر دارد، پس درخت خیلی «پهن و کوتاه» است.
• جدولی با ده‌ها میلیون ردیف معمولاً فقط ۳ یا ۴ سطح دارد؛ یعنی هر جست‌وجوی نقطه‌ای با ۳ یا ۴ خواندن صفحه تمام می‌شود و صفحه‌های بالایی همیشه در حافظه (buffer pool) هستند.
• برگ‌ها به هم زنجیر شده‌اند، پس پیمایش بازه (BETWEEN، >، ORDER BY) پس از پیدا کردن نقطه‌ی شروع، فقط خواندن پشت‌سرهم است.

Clustered Index: جدول همان ایندکس است

در InnoDB برگ‌های ایندکس کلید اصلی کل ردیف را در خود دارند؛ جدول جدا از این ایندکس وجود ندارد. هر ایندکس دیگر (secondary index) در برگ‌هایش فقط ستون‌های ایندکس به‌علاوه‌ی مقدار کلید اصلی را نگه می‌دارد.

CREATE TABLE orders (
  id          BIGINT UNSIGNED AUTO_INCREMENT PRIMARY KEY,   -- clustered
  customer_id INT UNSIGNED NOT NULL,
  status      VARCHAR(20) NOT NULL,
  created_at  DATETIME NOT NULL,
  total_amount DECIMAL(15,0) NOT NULL,
  INDEX ix_customer (customer_id)       -- برگ‌ها: (customer_id, id)
);

-- این کوئری دو مرحله دارد:
-- ۱) در ix_customer همه‌ی idهای مشتری 42 پیدا می‌شود
-- ۲) برای هر id یک جست‌وجو در clustered index تا بقیه‌ی ستون‌ها خوانده شود
SELECT created_at, total_amount FROM orders WHERE customer_id = 42;

مرحله‌ی دوم (lookup به کلید اصلی) هزینه دارد. اگر مشتری ۵ سفارش دارد ناچیز است؛ اگر شرط ۳۰٪ جدول را برگرداند، بهینه‌ساز ترجیح می‌دهد کل جدول را پیمایش کند و ایندکس را کنار بگذارد. به همین دلیل ایندکس روی ستون کم‌تنوع (مثل جنسیت یا وضعیت دوحالته) به‌تنهایی معمولاً بی‌فایده است.

دیدن و سنجیدن ایندکس‌ها

SHOW INDEX FROM orders;          -- Cardinality: تخمین تعداد مقادیر متمایز
ANALYZE TABLE orders;            -- به‌روزرسانی آمار ایندکس‌ها

-- اندازه‌ی هر ایندکس به مگابایت
SELECT index_name,
       ROUND(stat_value * @@innodb_page_size / 1024 / 1024, 1) AS size_mb
FROM mysql.innodb_index_stats
WHERE database_name = 'carpet_shop' AND table_name = 'orders'
  AND stat_name = 'size';

هزینه‌ی ایندکس

هر ایندکس خواندن را سریع و نوشتن را کندتر می‌کند: هر INSERT، UPDATE روی ستون ایندکس‌دار و DELETE باید همه‌ی ایندکس‌ها را به‌روز کند و فضای دیسک و buffer pool مصرف می‌کند. هدف «ایندکس روی همه‌ی ستون‌ها» نیست؛ ایندکس برای کوئری‌های واقعی و پرتکرار است.

نکته‌هایی که کمتر کسی می‌داند

• چون کلید اصلی در هر ایندکس ثانویه کپی می‌شود، کلید اصلی CHAR(36) با utf8mb4 می‌تواند حجم همه‌ی ایندکس‌ها را چند برابر کند؛ یکی دیگر از دلایل BIGINT یا BINARY(16).
• ایندکس ثانویه به‌طور ضمنی کلید اصلی را در انتها دارد؛ پس INDEX (customer_id) برای WHERE customer_id = 42 ORDER BY id مرتب‌سازی جداگانه لازم ندارد.
• Cardinality در SHOW INDEX تخمینی از نمونه‌گیری چند صفحه است و ممکن است بعد از تغییرات بزرگ داده، بهینه‌ساز را به اشتباه بیندازد؛ پس از ورود دسته‌ای حجیم ANALYZE TABLE بزنید.
• InnoDB یک Adaptive Hash Index هم دارد که روی صفحه‌های داغ خودکار ساخته می‌شود؛ در 8.4 به‌طور پیش‌فرض خاموش است، چون در بار هم‌زمان بالا خودش گلوگاه قفل می‌شد.
• ایندکس‌های تکراری رایج‌اند: INDEX (a) وقتی INDEX (a, b) هم وجود دارد زائد است. SELECT * FROM sys.schema_redundant_indexes; آن‌ها را نشان می‌دهد.