ایندکس‌های دیتابیس Database Indexes

به یک کتاب چاپی فکر کنید. برای پیدا کردن یک موضوع، همهٔ صفحه‌ها را نمی‌خوانید — می‌روید سراغ فهرست پایان کتاب: موضوع، شمارهٔ صفحه، و یک‌راست می‌پرید همان‌جا. ایندکس دیتابیس دقیقاً همین کار را با جدول شما می‌کند. Think of a paper book. To find one topic, you don't read every page — you flip to the index at the back: topic, page number, jump straight there. A database index does exactly this for your table.

-- one column, one line
CREATE INDEX IX_Products_Name
    ON dbo.Products(Name);

دیتابیس‌ها حافظه را در تکه‌هایی با اندازه ثابت می‌خوانند که به آن‌ها صفحه می‌گویند — در SQL Server هر صفحه ۸ کیلوبایت. برای جواب دادن به یک کوئری دو راه اساسی وجود دارد: Databases read storage in fixed-size chunks called pages — 8 KB each in SQL Server. There are two basic ways to answer a query:

اسکن کامل همهٔ صفحه‌ها را پشت‌سرهم می‌خواند و هر سطر را چک می‌کند. ساده است، اما هزینه‌اش با اندازهٔ جدول رشد می‌کند.
جست‌وجوی ایندکسی (seek) از روی چند صفحهٔ ایندکس عبور می‌کند و یک‌راست به سطرهای منطبق می‌پرد. هزینه‌اش حتی روی جدول‌های غول‌پیکر به‌زحمت رشد می‌کند. A full scan reads every page, one after another, and checks every row. Simple, but the cost grows with the table. An
index seek walks a few pages of the index, then jumps straight to the matching rows. Its cost barely grows, even on huge tables.

SET STATISTICS IO ON;

SELECT Id, Total FROM dbo.Orders
WHERE CustomerId = 1042;
-- before: Table 'Orders'. Scan count 1, logical reads 12045

CREATE INDEX IX_Orders_CustomerId
    ON dbo.Orders(CustomerId);

-- same query again:
-- after:  Table 'Orders'. Scan count 1, logical reads 9

در رختکن، کت‌تان را تحویل می‌دهید و یک شماره می‌گیرید. بعداً همان شماره را نشان می‌دهید و کت‌تان را بی‌درنگ پس می‌گیرید — کسی دنبال چیزی نمی‌گردد. شماره، مستقیم به قلابِ درست می‌رسد. ایندکس هش هم دقیقاً همین‌طور کار می‌کند. At a coat check, you hand over your coat and get a number. Later, that number leads straight to the right hook — no searching. A hash index works exactly like this.

یک تابع هش، کلید شما مثلاً user:42 را می‌گیرد و یک عدد از آن می‌سازد. دیتابیس این عدد را روی تعداد سطل‌ها تقسیم می‌کند و باقیماندهٔ آن مشخص می‌کند که کلید در کدام سطل می‌نشیند؛ مثلاً سطل شمارهٔ ۵ از ۸. خودِ مقدار (یا اشاره‌گر به سطر) دقیقاً در همان سطل ذخیره می‌شود. A hash function takes your key say user:42 and produces a number. The database divides this number by the bucket count and uses the remainder to decide which bucket the key lands in — for instance, bucket 5 out of 8. The value (or a pointer to the row) is stored right there in that bucket.

پیدا کردنِ یک کلیدِ مشخص با این روش، سرعت ثابتی دارد (O(1)). یعنی فرقی نمی‌کند جدول شما ۱۰۰ سطر داشته باشد یا ۱۰۰ میلیون — موتور همیشه فقط یک سطل را باز می‌کند و جواب را می‌گیرد. Finding one exact key with this method is constant time (O(1)). Whether your table has 100 rows or 100 million, the engine always opens just one bucket and retrieves the answer.

۸ سطل — هر کلید فقط در یکی می‌نشیند و هیچ ترتیبی بین سطل‌ها نیست. 8 buckets — every key lands in exactly one, and there is no order between buckets.

اما یک گرفتاری بزرگ دارد: ایندکس هش نمی‌تواند کوئری‌های range را جواب بدهد. پرسیدنِ «هر کلیدی بین ۱۰ تا ۲۰ را بده» نیاز دارد داده مرتب باشد، و تابع هش همین ترتیب را دور می‌ریزد. سطل ۳ به هیچ معنای مفیدی «کنار» سطل ۴ نیست. یعنی نه > و نه <، نه BETWEEN، نه ORDER BY و نه پیشوندی مثل LIKE 'ab%'. The big catch: hash indexes cannot answer range queries. Asking "every key between 10 and 20" needs sorted data, and hashing throws that order away. Bucket 3 is not "next to" bucket 4 in any useful sense — no >, no <, no BETWEEN, no ORDER BY, no LIKE 'ab%'.

// Dictionary is a hash index in RAM
var price = new Dictionary<string, decimal>();
price["SKU-42"] = 19.99m;     // write: O(1)
var p = price["SKU-42"];      // read:  O(1)

// "all keys greater than SKU-42"?
// → no order stored. Walk EVERY entry.

-- only on MEMORY_OPTIMIZED tables
CREATE TABLE dbo.SessionCache (
  SessionId UNIQUEIDENTIFIER NOT NULL,
  Payload   NVARCHAR(4000),

  INDEX IX_Session HASH (SessionId)
      WITH (BUCKET_COUNT = 131072)
) WITH (MEMORY_OPTIMIZED = ON);

اینجا سه اصطلاح یاد می‌گیرید:Three terms to learn here:

به‌همین دلیل، سیستم‌هایی که نوشتن در آنها حرف اول را می‌زند، از این خانواده استفاده می‌کنند. نام‌هایی مثل Cassandra، HBase، ScyllaDB، RocksDB و LevelDB را ممکن است شنیده باشید — همه‌ی آنها موتورهایی LSM-محور هستند. نقطه‌ضعفشان خواندن است، چون یک مقدار ممکن است در هرکدام از چندین SSTable باشد؛ پس هر خواندن شاید چند فایل را جست‌وجو کند. دو ترفند این مشکل را کم می‌کند: ۱ همیشه اول جدیدترین فایل را چک کن (چون داده‌ی جدیدتر برنده است)؛ ۲ از Bloom Filter استفاده کن — ساختاری کوچک که جواب می‌دهد «قطعاً این کلید در این فایل نیست» تا موتور بدون اینکه دیسک را لمس کند، آن فایل را رد کند. This is why write-heavy systems use this family. You may have heard names like Cassandra, HBase, ScyllaDB, RocksDB and LevelDB — all are LSM-based engines. Their weak spot is reads, because a value might be in any of several SSTables. Two tricks help: 1 always check the newest file first (newer data wins); 2 use a Bloom Filter — a tiny structure that says "this key is definitely not here", so the engine skips that file without touching disk.

برای اینکه در هنگامِ خرابی (crash) داده‌ای از دست نرود، هر نوشتن، علاوه بر memtable، به یک لاگِ کوچک و فقط-اضافه‌شونده (append-only) هم اضافه می‌شود. به این لاگ، WAL (Write-Ahead Log) می‌گویند. اگر برق برود، موتور هنگام راه‌اندازی مجدد، این لاگ را دوباره اجرا می‌کند و داده‌های ازدست‌رفته‌ی RAM را بازیابی می‌کند. در ایستگاه ۰۵ (درخت B) دوباره با همین مفهوم WAL آشنا می‌شوید. For durability, every write is also appended to a small, append-only log called the WAL (Write-Ahead Log). If power fails, the engine replays this log on startup to recover any data lost from RAM. You'll meet the same WAL concept again at stop 05 (B-Trees).

درخت B یک درخت است که از صفحه ساخته شده. هر گره، چند کلیدِ مرتب و چند اشاره‌گر به گره‌های فرزند دارد. دو ویژگی، آن را از بقیهٔ ساختارها جدا می‌کند: A B-tree is a tree made of pages. Each node holds several sorted keys and pointers to child nodes. Two features set it apart:

پس با فقط ۴ سطح، می‌توانیم ۸ میلیارد کلید را پوشش دهیم. این یعنی برای پیدا کردن هر کلیدی، فقط کافی است از ریشه شروع کنیم، ۳ بار تصمیم بگیریم، و به برگ برسیم — یعنی حداکثر ۴ صفحه خواندن. این همان جادویِ درخت B است: عمق با لگاریتمِ تعداد سطرها رشد می‌کند، نه با خودِ تعداد سطرها. So with just 4 levels, we can cover 8 billion keys. That means to find any key, we just start at the root, make 3 decisions, and reach the leaf — at most 4 page reads. That's the magic of the B-tree: depth grows with the logarithm of the row count, not with the row count itself.

فقط ۳ تا ۴ صفحه کافی است تا از ریشه به هر سطری در یک جدولِ میلیاردی برسید. هر سطح، تعداد کلیدها را در fan-out ضرب می‌کند — به همین دلیل عمقِ درخت با بزرگ‌شدن جدول، خیلی کم رشد می‌کند. Just 3 to 4 pages are enough to go from the root to any row in a billion-row table. Each level multiplies the total by the fan-out — that's why the depth grows so slowly as the table grows.

کوئری‌های محدوده (Range) چطور کار می‌کنند؟
فرض کنید می‌خواهید همهٔ سفارش‌های بین تاریخ ۱ تا ۱۵ مرداد را پیدا کنید. موتور اول از ریشه شروع می‌کند و تا برگی پایین می‌رود که شروعِ محدوده (۱ مرداد) در آن قرار دارد. بعد از آن، به‌جای اینکه دوباره از ریشه بالا برود، از زنجیرهٔ برگ‌ها (همان خط‌چین‌هایی که در شکل دیدید) به سمت راست حرکت می‌کند و برگ‌ها را یکی‌یکی می‌خواند تا به انتهای محدوده (۱۵ مرداد) برسد. این زنجیره است که درخت B را برای BETWEEN، >، < و ORDER BY به یک ابزارِ بی‌نظیر تبدیل می‌کند. How range queries work:
Suppose you want all orders between August 1st and 15th. The engine starts at the root, descends to the leaf that holds the start of the range (Aug 1). Then, instead of climbing back up, it walks right along the leaf chain (the dashed lines you saw in the diagram), reading leaves one by one until it reaches the end of the range (Aug 15). This chain is what makes B-trees excellent at BETWEEN, >, <, and ORDER BY.

یک نکتهٔ حیاتی: درخت B صفحه‌ها را درجا به‌روز می‌کند — یعنی تغییر را مستقیماً روی همان صفحهٔ دیسک می‌نویسد. اگر در حین نوشتن، برق برود یا سیستم crash کند، آن صفحه ممکن است نصفه‌نیمه باقی بماند و خراب شود. برای جلوگیری از این اتفاق، دیتابیس قبل از اینکه هر صفحه‌ای را تغییر دهد، آن تغییر را به یک فایلِ فقط-اضافه‌شونده به نام WAL (Write-Ahead Log) اضافه می‌کند. اگر crash رخ دهد، موتور هنگام راه‌اندازی مجدد، این لاگ را از اول می‌خواند و تغییراتِ ناتمام را دوباره اعمال می‌کند. در SQL Server به این لاگ، لاگ تراکنش (Transaction Log) می‌گویند — همان فایلی که گاهی بزرگ می‌شود و حالا می‌دانید که دقیقاً برای چیست. A critical point: B-trees update pages in place — they write changes directly to the disk page. If power fails mid-write, that page could be left half-finished and corrupted. To prevent this, the database appends every change to an append-only file called the WAL (Write-Ahead Log) before touching the actual page. If a crash occurs, the engine replays this log on startup to reapply any incomplete changes. In SQL Server, this is the transaction log — the file that sometimes grows large, and now you know exactly why.

دو مفهوم، بیشترِ بحث‌های انتخابِ موتور را شکل می‌دهند: Write Amplification (هزینه‌ی نوشتن) و Read Amplification (هزینه‌ی خواندن). نوارهای زیر نشان می‌دهند که هر موتور در این دو معیار، چطور عمل می‌کند. Two concepts shape most engine-selection debates: Write Amplification (write cost) and Read Amplification (read cost). The bars below show how each engine performs on these two metrics.

-- B-Tree
B-Tree:  Changing 100 bytes -> rewrites an entire 8 KB page + a log entry
         -> Write Amplification, visible right here

-- LSM
LSM:     Changing 100 bytes -> appended to memtable in RAM (cheap)
         ... but this data will be rewritten 10–30 times later during compaction
         The bill arrives in installments over time.

حالا یک هزینهٔ پنهان اینجا وجود دارد: وقتی یک ایندکس غیرخوشه‌ای را می‌خوانید، برگِ آن به شما می‌گوید «این کلید را پیدا کردم، حالا برو به جدول اصلی تا بقیه‌ی داده‌ها را بیاوری». به این پرشِ اضافی، Key Lookup (یا در کتاب‌های قدیمی‌تر، Bookmark Lookup) می‌گویند. برای پیدا کردنِ چند سطر، این پرش ارزان است؛ اما اگر کوئری شما صدها یا هزاران سطر برگرداند، این پرش‌ها جمع می‌شوند و هزینه‌ی سنگینی ایجاد می‌کنند. Now there's a hidden cost: when you read a non-clustered index, its leaf tells you "I found this key — now go to the main table to get the rest of the data." This extra hop is called a Key Lookup (or Bookmark Lookup in older books). For a few rows, this hop is cheap; but if your query returns hundreds or thousands of rows, these lookups add up and become expensive.

b.Entity<Order>(o =>
{
    // PK → clustered by default
    o.HasKey(x => x.Id);

    o.HasIndex(x => x.CustomerId)
     .Include(x => new { x.Total }); // covering
});

CREATE INDEX IX_Orders_CustomerId
    ON dbo.Orders(CustomerId)
    INCLUDE (Total);

-- need a different sort for the table?
CREATE CLUSTERED INDEX CX_Orders
    ON dbo.Orders(OrderDate);

یک ایندکس ترکیبی، بیش از یک ستون را به‌عنوان کلید دارد — مثلاً (Status, OrderDate). اما ترتیبِ این ستون‌ها بسیار مهم است، به‌خاطر قاعدهٔ پیشوند چپ‌ترین: ایندکس ابتدا بر اساسِ ستونِ اول مرتب می‌شود، سپس درونِ هر گروه، بر اساسِ ستونِ دوم، و به‌همین ترتیب. اگر ستونِ اول را در کوئری‌تان رد کنید، ترتیبِ بقیه‌ی ستون‌ها برای موتور بی‌فایده خواهد بود. A composite index uses more than one column as the key — e.g. (Status, OrderDate). But the order of these columns matters enormously, because of the leftmost-prefix rule: the index is sorted by the first column, then within each group by the second, and so on. If you skip the first column in your query, the rest of the sort becomes useless to the engine.

انتخاب‌گری (Selectivity) یعنی: «یک ستون، چقدر جست‌وجو را محدود می‌کند؟» فرمولش ساده است: تعدادِ مقادیرِ متمایز ÷ تعدادِ کلِ سطرها. هرچه این عدد به ۱ نزدیک‌تر باشد، ستون انتخاب‌گریِ بالاتری دارد (یعنی تقریباً یکتا است و خوب فیلتر می‌کند). هرچه به ۰ نزدیک‌تر باشد، انتخاب‌گریِ پایین‌تری دارد (یعنی خیلی ضعیف فیلتر می‌کند). Selectivity measures: "how much does this column narrow down the search?" The formula is simple: distinct values ÷ total rows. The closer to 1, the higher the selectivity (nearly unique, great for filtering). The closer to 0, the lower the selectivity (barely filters, weak alone).

CREATE INDEX IX_Orders_Status_Date
    ON dbo.Orders(Status, OrderDate) INCLUDE (Total);

-- HIT: equality on leftmost, then range
WHERE Status = 'Paid' AND OrderDate >= '2026-08-01'

-- HIT: leftmost alone is fine
WHERE Status = 'Paid'

-- MISS: leftmost column skipped
WHERE OrderDate >= '2026-08-01'

o.HasIndex(x => new { x.Status, x.OrderDate });
// first property = leftmost key column.
// Swap them, and you built a different index.

صفحه را ببندید و با کلمات خودتان جواب بدهید، بعد کلیک کنید و مقایسه کنید. اگر سوالی شما را گیر انداخت، به ایستگاه همان سوال بپرید. Close the page, answer in your own words, then click to compare. If one stumps you, hop back to its stop.