بررسی عمیق ایندکس‌گذاری پایگاه داده برای مصاحبه‌های طراحی سیستم

ایندکس‌گذاری پایگاه داده

در این فصل یاد می‌گیریم ایندکس‌گذاری پایگاه داده چطور کار می‌کند و چطور می‌توان کوئری‌ها را بهینه کرد.

کارایی پایگاه داده می‌تواند برنامه‌های مدرن را بسازد یا خراب کند. فکر کنید برای پیدا کردن پروفایل یک کاربر با ایمیل در جدولی با میلیون‌ها رکورد چه لازم است. بدون هیچ بهینه‌سازی، پایگاه داده باید همه سطرها را پشت سر هم بررسی کند و هر رکورد را اسکن کند تا به رکورد منطبق برسد. برای جدولی با میلیون‌ها سطر این به‌شکل دردناکی کند است. مثل این است که برای پیدا کردن یک رمان مشخص، تک‌تک کتاب‌های یک کتابخانه را بگردید.

اینجاست که ایندکس‌ها به کار می‌آیند. ایندکس‌ها ساختارهای داده جداگانه‌ای هستند که برای جستجو بهینه شده‌اند. با نگه داشتن این ساختارها، پایگاه داده می‌تواند رکوردهای موردنیاز را بدون بررسی همه سطرها سریع پیدا کند. از پیدا کردن محصول در کاتالوگ فروشگاه آنلاین تا بارگذاری پروفایل کاربران در شبکه اجتماعی، ایندکس‌ها جستجوی سریع را ممکن می‌کنند.

دانستن این‌که چه زمانی ایندکس اضافه کنیم، روی کدام ستون‌ها و از چه نوعی، بخش مهمی از طراحی سیستم است. انتخاب ایندکس مناسب اغلب تمرکز اصلی مصاحبه است. از مهندسان میدلول انتظار می‌رود استراتژی‌های پایه ایندکس‌گذاری را بفهمند. برای مهندسان سطح Staff، تسلط بر انواع مختلف ایندکس و مصالحه‌های آن‌ها ضروری است.

این بررسی عمیق نحوه کار ایندکس‌های پایگاه داده در پشت صحنه و انواع مختلف آن‌ها را پوشش می‌دهد. با مفاهیم اصلی نحوه ذخیره و دسترسی به ایندکس‌ها شروع می‌کنیم و بعد سراغ انواع مشخص مثل B-Tree، ایندکس هش، ایندکس مکانی و موارد دیگر می‌رویم. برای هر نوع، نقاط قوت، محدودیت‌ها و زمان استفاده از آن در مصاحبه‌های طراحی سیستم را می‌گوییم.

اول ببینیم پایگاه‌های داده چطور ایندکس‌ها را ذخیره می‌کنند و چطور از آن‌ها برای کارآمد کردن کوئری‌ها استفاده می‌کنند.

ایندکس‌گذاری و سازمان‌دهی داده در مصاحبه‌های سبک زیرساخت اهمیت بیشتری دارد. برای نقش‌های full-stack و محصول‌محور، احتمالاً فقط به درک پایه از زمان و چرایی استفاده از ایندکس نیاز دارید. عمقی که اینجا می‌گوییم از آنچه معمولاً در مصاحبه‌های full-stack پرسیده می‌شود بیشتر است، اما فهمیدن اصول به شما کمک می‌کند هنگام طراحی و بهینه‌سازی برنامه‌هایتان تصمیم‌های بهتری بگیرید.

ایندکس‌های پایگاه داده چطور کار می‌کنند

وقتی داده را در پایگاه داده ذخیره می‌کنیم، در نهایت به‌صورت مجموعه‌ای از فایل‌ها روی دیسک نوشته می‌شود. داده‌های جدول اصلی معمولاً به‌صورت heap file ذخیره می‌شوند، یعنی مجموعه‌ای از سطرها بدون ترتیب مشخص. مثل دفترچه‌ای که هر چیز را به‌محض رسیدن پشت سر هم در آن می‌نویسید.

ذخیره‌سازی فیزیکی و الگوهای دسترسی

مگر این‌که برای نقش مرتبط با درون‌ساخت پایگاه داده مصاحبه می‌دهید، جزئیات این بخش در مصاحبه پرسیده نمی‌شود. با این حال پایه مهمی برای فهمیدن این است که چرا به ایندکس نیاز داریم.

پایگاه‌های داده مدرن با چالش جالبی روبه‌رو هستند. باید حجم عظیمی از داده را ذخیره کنند و سریع به آن دسترسی بدهند. داده روی دیسک (معمولاً SSDهای امروزی) زندگی می‌کند، اما فقط وقتی می‌توانیم پردازشش کنیم که در حافظه باشد. یعنی هر کوئری باید داده را از دیسک در RAM بارگذاری کند.

وقتی بدون ایندکس کوئری می‌زنیم، باید همه صفحه‌های داده را یکی‌یکی اسکن کنیم و هر کدام را در حافظه بارگذاری کنیم تا ببینیم همان چیزی است که دنبالش هستیم. با میلیون‌ها صفحه، یعنی میلیون‌ها خواندن (نسبتاً) کند از دیسک فقط برای پیدا کردن یک رکورد. مثل این است که برای پیدا کردن یک کلمه مشخص، صفحه‌به‌صفحه یک کتاب غول‌پیکر را ورق بزنید.

پایگاه‌های داده مدرن بهینه‌سازی‌هایی مثل prefetching و caching دارند که دسترسی تصادفی را سریع‌تر می‌کنند، اما اصل مطلب هنوز صادق است. اسکن متوالی همه صفحه‌های داده بسیار کند است.

اما با ایندکس‌ها الگوی دسترسی‌مان را عوض می‌کنیم. به‌جای خواندن متوالی هر صفحه از داده، ایندکس‌ها مسیر ساختاریافته‌ای برای رسیدن مستقیم به داده موردنیاز فراهم می‌کنند. به ما کمک می‌کنند تعداد صفحه‌هایی را که باید از ذخیره‌گاه بخوانیم حداقل کنیم و دقیقاً می‌گویند کدام صفحه‌ها داده موردنظر ما را دارند. این مثل فرق بین ورق زدن تک‌تک صفحه‌های کتاب و استفاده از فهرست مطالب برای پریدن مستقیم به صفحه‌های مرتبط است.

امروزه SSDها رایج‌اند، اما باید توجه کرد که دسترسی تصادفی هنوز حتی در SSD هم به‌طور محسوسی کندتر از دسترسی متوالی است. این تصور غلط رایجی است. فاصله کارایی از HDD کمتر است، ولی هنوز کاملاً واقعی است. و برای سیستم‌هایی که هنوز از HDD استفاده می‌کنند، به‌خصوص با مجموعه داده بزرگ، این اختلاف کارایی حتی بیشتر می‌شود و ایندکس‌گذاری درست کاملاً حیاتی است.

هزینه

اما ایندکس‌ها رایگان نیستند و مصالحه‌هایی دارند. هر ایندکسی که می‌سازیم فضای دیسک اضافه می‌خواهد، گاهی تقریباً به اندازه خود داده اصلی.

کارایی نوشتن هم ضربه می‌خورد. وقتی سطر جدید درج می‌کنیم یا سطر موجود را به‌روز می‌کنیم، پایگاه داده باید فقط جدول اصلی را به‌روز نکند، بلکه همه ایندکس‌های روی آن را هم باید به‌روز کند. با چند ایندکس، یک عملیات نوشتن می‌تواند چند نوشتن روی دیسک راه بیندازد.

پس چه زمانی ایندکس‌ها بیشتر ضرر می‌زنند تا کمک کنند؟ مورد کلاسیک، جدولی است که نوشتن زیاد و خواندن کم دارد. جدولی را فکر کنید که مدام رکورد جدید درج می‌کنیم اما به‌ندرت رکوردهای قدیمی را جستجو می‌کنیم. اینجا سربار نگهداری ایندکس‌ها ممکن است ارزشش را نداشته باشد. به‌طور مشابه برای جدول‌های کوچک با فقط چند صد سطر، هزینه نگهداری ایندکس و پیمایش ساختار آن ممکن است از هزینه یک اسکن متوالی ساده بیشتر باشد.

در واقعیت اثر ایندکس‌ها روی حافظه اغلب بزرگ‌تر از واقعیت تصور می‌شود. پایگاه‌های داده مدرن مدیریت هوشمند buffer pool دارند که اثر چند ایندکس را کم می‌کند. با این حال، هنوز ایده خوبی است که استفاده از ایندکس‌ها را با دقت زیر نظر داشته باشید و از ساختن ایندکس‌های غیرضروری که مزیت محسوسی نمی‌دهند پرهیز کنید.

انواع ایندکس

ایندکس‌های زیادی وجود دارد که بیشترشان در «دم توزیع» قرار می‌گیرند و به‌ندرت استفاده می‌شوند، مگر در کاربردهای تخصصی. به‌جای شمردن همه انواع ایندکس، روی رایج‌ترین انواعی تمرکز می‌کنیم که در مصاحبه‌های طراحی سیستم مطرح می‌شوند.

B-Tree

ایندکس‌های B-Tree رایج‌ترین نوع ایندکس پایگاه داده‌اند و روش کارآمدی برای سازمان‌دهی داده برای جستجو و به‌روزرسانی سریع فراهم می‌کنند. این کار را با نگه داشتن یک ساختار درختی متعادل انجام می‌دهند که تعداد خواندن دیسک لازم برای پیدا کردن هر داده را حداقل می‌کند.

ساختار B-Tree

B-Tree درختی خودمتعادل‌شونده است که داده مرتب را نگه می‌دارد و درج، حذف و جستجوی کارآمد را ممکن می‌کند. برخلاف درخت دودویی که هر گره حداکثر دو فرزند دارد، گره‌های B-Tree می‌توانند فرزندان زیادی داشته باشند، معمولاً صدها فرزند. هر گره آرایه مرتبی از کلیدها و اشاره‌گرها دارد که طوری ساخته شده است که خواندن دیسک را حداقل کند.

هر گره در B-Tree از قوانین سختگیرانه‌ای پیروی می‌کند.

• همه گره‌های برگ باید در یک عمق باشند.
• هر گره (جز ریشه) باید حدوداً حداقل نیمی از ظرفیتش پر باشد. تعداد کلیدهای هر گره بین m/2 و m-1 است، که m ترتیب (order) درخت است.
• گره‌ای با k کلید باید دقیقاً k+1 فرزند داشته باشد.
• کلیدهای داخل هر گره به‌ترتیب مرتب نگه داشته می‌شوند.

این ساختار از این نظر هوشمندانه است که کاملاً با نحوه ذخیره داده روی دیسک در پایگاه‌های داده هماهنگ است. اندازه هر گره طوری است که در یک صفحه دیسک (معمولاً ۸ کیلوبایت) جا شود و کارایی I/O را به حداکثر برساند. وقتی PostgreSQL باید رکوردی با id=350 را پیدا کند، شاید فقط لازم باشد ۲ تا ۳ صفحه از دیسک بخواند، یعنی گره ریشه، شاید یک گره داخلی و در نهایت گره برگ.

نمونه‌های دنیای واقعی

B-Treeها در پایگاه‌های داده مدرن همه‌جا هستند. PostgreSQL تقریباً برای همه‌چیز از آن‌ها استفاده می‌کند. کلیدهای اصلی، قیدهای یکتایی (unique constraint) و بیشتر ایندکس‌های معمولی همه B-Tree هستند.

وقتی جدولی مثل این را در PostgreSQL می‌سازید:

CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    email VARCHAR(255) UNIQUE
);

PostgreSQL به‌طور خودکار دو ایندکس B-Tree می‌سازد، یکی برای کلید اصلی و دیگری برای قید یکتایی ایمیل. این B-Treeها ترتیب مرتب را نگه می‌دارند که هم برای بررسی یکتایی و هم برای جستجوی بازه‌ای بسیار مهم است.

Sort key در DynamoDB هم به‌شکل نوعی B-Tree پیاده‌سازی شده است که جستجوی بازه‌ای کارآمد داخل یک پارتیشن را ممکن می‌کند. به همین دلیل DynamoDB می‌تواند کوئری‌هایی مثل «همه سفارش‌های کاربر X بین تاریخ Y و Z» را کارآمد انجام دهد. ساختار B-Tree اسکن بازه‌ای را سریع می‌کند.

حتی MongoDB با مدل سندی‌اش برای ایندکس‌هایش از B-Tree استفاده می‌کند (دقیق‌تر B+Tree، گونه‌ای که همه داده در گره‌های برگ ذخیره می‌شود). وقتی در MongoDB این‌طور ایندکس می‌سازید:

db.users.createIndex({ "email": 1 });

در واقع B-Treeای می‌سازید که مقدارهای ایمیل را به محل سندها نگاشت می‌کند.

چرا B-Tree انتخاب پیش‌فرض است

B-Tree به انتخاب پیش‌فرض برای بیشتر ایندکس‌های پایگاه داده تبدیل شده، چون در هر چیزی که پایگاه‌های داده نیاز دارند عالی است.

• ترتیب مرتب را حفظ می‌کند و جستجوی بازه‌ای و عملیات ORDER BY را کارآمد می‌کند.
• خودمتعادل‌شونده است و حتی با رشد داده، کارایی قابل‌پیش‌بینی را تضمین می‌کند.
• با هماهنگ کردن ساختارش با نحوه ذخیره داده در پایگاه داده، I/O دیسک را حداقل می‌کند.
• جستجوی برابری (email = 'x') و جستجوی بازه‌ای (age > 25) را به یک اندازه خوب انجام می‌دهد.
• حتی با درج و حذف تصادفی هم متعادل می‌ماند و از افت‌های ناگهانی کارایی که در ساختارهای درختی ساده‌تر می‌بینید پرهیز می‌کند.

اگر در مصاحبه هستید و باید تصمیم بگیرید از کدام ایندکس استفاده کنید، B-Tree انتخاب مطمئنی است.

LSM Tree (Log-Structured Merge Tree)

B-Treeها برای بارهای کاری متعادل عالی هستند، اما وقتی باید تعداد زیادی نوشتن انجام دهید چه می‌شود؟ سیستمی مثل DataDog را فکر کنید که میلیون‌ها متریک در ثانیه از هزاران سرور می‌گیرد. هر خوانش CPU، آمار حافظه و تعداد خطا باید فوراً ذخیره شود.

با B-Tree هر نوشتن یعنی پیدا کردن صفحه برگ مناسب، خواندنش در حافظه، به‌روز کردن آن و نوشتنش روی دیسک. برای چند هزار نوشتن در ثانیه این مشکلی ندارد. اما وقتی ۱۰۰ هزار نوشتن در ثانیه پردازش می‌کنید، این جستجوهای تصادفی دیسک گلوگاه می‌شوند. مثل به‌روز کردن یک کابینت بایگانی است که باید پوشه‌های پراکنده را یکی‌یکی پیدا کنید و تغییر دهید. در نهایت بیشتر وقتتان صرف جستجو می‌شود، نه ذخیره واقعی داده.

اینجا LSM Treeها واقعاً خوب کار می‌کنند. اما رویکرد کاملاً متفاوتی به ایندکس‌گذاری دارند. در B-Tree هر ایندکس ساختار جداگانه خودش را دارد و می‌توانید روی هر ستونی بسازید. LSM Tree این‌طور کار نمی‌کند. LSM Tree قالب ذخیره‌سازی کل جدول شماست که بر اساس کلید اصلی مرتب شده است. یک مسیر دسترسی بسیار سریع (جستجوی کلید اصلی) می‌گیرید و برای هر چیز دیگری باید داده را اسکن کنید.

LSM Treeها به‌جای به‌روزرسانی در محل (in-place) مثل B-Tree، از رویکرد append-only استفاده می‌کنند که برای بارهای کاری نوشتن‌سنگین ساخته شده است.

LSM Tree چطور کار می‌کند

LSM Tree مشکل نوشتن را با دسته‌بندی نوشتن‌ها در حافظه و فلاش کردن متوالی آن‌ها روی دیسک حل می‌کند. به‌جای نوشتن فوری هر به‌روزرسانی روی دیسک مثل B-Tree، تغییرات را در حافظه بافر می‌کند و در تکه‌های بزرگ می‌نویسد. این کار نوشتن‌های تصادفی کوچک و زیاد را به نوشتن‌های متوالی بزرگ و کم تبدیل می‌کند و کارایی را بالا می‌برد.

وقتی در پایگاه داده‌ای با LSM Tree می‌نویسید این اتفاق می‌افتد.

1. Memtable (در حافظه): نوشتن‌های جدید وارد ساختاری در حافظه به نام memtable می‌شوند، که معمولاً با ساختار داده مرتبی مثل درخت قرمز-سیاه یا skip list پیاده می‌شود. چون همه‌چیز در RAM است، بسیار سریع است.
2. Write-Ahead Log (WAL): برای تضمین دوام، هر نوشتن به یک WAL روی دیسک هم اضافه می‌شود. این یک عملیات append متوالی است که خیلی از نوشتن تصادفی سریع‌تر است.
3. فلاش به SSTable: وقتی memtable به اندازه مشخصی رسید (اغلب چند مگابایت)، تغییرناپذیر می‌شود و به‌صورت یک Sorted String Table (SSTable) تغییرناپذیر روی دیسک فلاش می‌شود. این یک نوشتن متوالی است که می‌تواند مگابایت‌ها داده را یک‌جا بنویسد.
4. Compaction: با گذشت زمان SSTableهای زیادی روی دیسک جمع می‌شوند. یک فرایند پس‌زمینه به نام compaction به‌طور دوره‌ای این فایل‌ها را ادغام می‌کند و ورودی‌های تکراری و حذف‌شده را پاک می‌کند. این کار تعداد فایل‌ها را قابل‌مدیریت نگه می‌دارد و کارایی خواندن را حفظ می‌کند.

نتیجه این است که سرعت نوشتن فوق‌العاده زیاد می‌شود، چون فقط به حافظه و یک فایل log اضافه می‌کنید. حتی هنگام فلاش کردن روی دیسک هم به‌جای جستجوی مکان‌های تصادفی، تکه‌های بزرگ متوالی می‌نویسید.

هزینه برای خواندن

مثل همیشه این مزیت‌ها هزینه دارند. LSM Tree در نوشتن عالی است، اما خواندن را پیچیده‌تر می‌کند. یادتان هست B-Tree می‌توانست هر رکوردی را فقط با ۲ تا ۳ خواندن از دیسک پیدا کند؟ با LSM Tree داستان فرق می‌کند.

وقتی برای کلید مشخصی کوئری می‌زنید، پایگاه داده باید چند جا را بررسی کند.

1. اول memtable: آیا داده در بافر حافظه فعلی هست؟
2. بعد memtableهای تغییرناپذیر: آیا memtableهایی منتظر فلاش شدن هستند؟
3. در نهایت همه SSTableهای روی دیسک: از جدیدترین (که بیشتر احتمال دارد داده اخیر را داشته باشد) شروع می‌کند و به عقب می‌رود.

یعنی در بدترین حالت ممکن است لازم باشد ده‌ها فایل را بررسی کند. مثل این است که دنبال سندی بگردید که ممکن است در کشوی میز، کابینت بایگانی یا یکی از چند جعبه بایگانی باشد و باید همه را بگردید.

واضح است که این ویژگی LSM Tree را برای هر گردش کاری که کارایی معقول خواندن می‌خواهد تقریباً غیرقابل‌استفاده می‌کند. برای کم کردن این مشکل، LSM Treeها معمولاً چند بهینه‌سازی دارند.

• Bloom Filter: هر SSTable یک Bloom Filter دارد. این ساختار داده احتمالاتی است که سریع می‌گوید یک کلید قطعاً در آن فایل نیست. این کار اجازه می‌دهد بیشتر SSTableها را بدون خواندن رد کنید. اگر Bloom Filter بگوید «شاید هست»، هنوز باید بررسی کنید، اما پاسخ منفی قطعی را حذف می‌کند.
• ایندکس پراکنده (Sparse Index): چون SSTableها مرتب هستند، ایندکس پراکنده‌ای نگه می‌دارند که بازه کلیدهای هر بلوک را می‌گوید. اگر دنبال user_id=500 هستید و SSTable فقط کلیدهای ۱۰۰۰ تا ۲۰۰۰ را دارد، می‌توانید آن را کامل رد کنید.
• استراتژی‌های Compaction: استراتژی‌های مختلف برای بارهای کاری مختلف بهینه شده‌اند. Size-Tiered Compaction تقویت نوشتن (write amplification) را حداقل می‌کند، اما ممکن است به بررسی فایل‌های بیشتری منجر شود. Leveled Compaction فایل‌های کمتری نگه می‌دارد، اما به بازنویسی‌های بیشتر و مکررتر نیاز دارد.

با وجود این بهینه‌سازی‌ها، LSM Tree اساساً کارایی خواندن را با کارایی نوشتن معاوضه می‌کند. این باعث می‌شود برای بارهای کاری نوشتن‌سنگین مثل پایگاه‌های داده سری زمانی، سیستم‌های logging و پلتفرم‌های تحلیلی عالی باشد. در این سیستم‌ها مدام داده تازه می‌گیرید اما کوئری‌ها کمترند یا می‌توانند تأخیر کمی بالاتر را تحمل کنند.

بینش کلیدی برای مصاحبه‌های طراحی سیستم این است که بدانید این مصالحه کی منطقی است. اگر سیستمی می‌سازید که خیلی بیشتر از خواندن می‌نویسد، مثل سیستم جمع‌آوری متریک، audit log یا پلتفرم داده اینترنت اشیا، LSM Tree احتمالاً انتخاب مناسبی است. اما برای اپلیکیشن رو به کاربر که هر بار بارگذاری صفحه چند کوئری راه می‌اندازد، B-Tree معمولاً کارایی بهتری دارد.

نمونه‌های دنیای واقعی

LSM Treeها بعضی از سیستم‌های نوشتن‌سنگین اینترنت را اجرا می‌کنند.

• Cassandra: میلیاردها رویداد تماشای Netflix را مدیریت می‌کند. وقتی برنامه‌ای را تماشا می‌کنید، آن داده بدون کند شدن پخش روی ذخیره‌گاه مبتنی بر LSM در Cassandra نوشته می‌شود.
• RocksDB (ساخته فیس‌بوک): موتور ذخیره‌سازی بسیاری از پایگاه‌های داده است. میلیون‌ها تعامل اجتماعی در ثانیه، یعنی لایک‌ها، پست‌ها و پیام‌ها، را مدیریت می‌کند که همه برای ماندگاری سریع روی LSM Tree نوشته می‌شوند.
• DynamoDB: هم از LSM Tree و هم از B-Tree استفاده می‌کند و موتور ذخیره‌سازی مناسب را برای هر بار کاری به‌طور خودکار انتخاب می‌کند. داده‌های نوشتن‌سنگین مثل خوانش حسگرهای اینترنت اشیا برای appendهای سریع به ذخیره‌گاه LSM می‌روند. داده‌های خواندن‌سنگین مثل کاتالوگ محصول برای جستجوی سریع در ذخیره‌گاه B-Tree قرار می‌گیرند. DynamoDB الگوهای دسترسی شما را زیر نظر دارد و در پشت صحنه بین موتورهای ذخیره‌سازی سوئیچ می‌کند.

ایندکس هش

با این‌که B-Treeها بر چشم‌انداز ایندکس‌گذاری غالب‌اند، ایندکس هش هدف تخصصی‌ای دارد. این ایندکس در کوئری‌های تطبیق دقیق (exact match) عالی است. ایندکس هش در واقع پیاده‌سازی پایدار (persistent) یک hash map است و با مصالحه انعطاف‌پذیری، جستجوی فوق‌سریع با زمان O(1) می‌دهد.

ایندکس هش چطور کار می‌کند

ایندکس هش در هسته‌اش فقط یک hash map است که مقدارهای ایندکس‌شده را به محل سطرها نگاشت می‌کند. پایگاه داده آرایه‌ای از bucketها را نگه می‌دارد که هر bucket می‌تواند چند جفت کلید و محل را ذخیره کند. هنگام ایندکس کردن یک مقدار، پایگاه داده آن را هش می‌کند تا مشخص شود اشاره‌گر به داده سطر در کدام bucket ذخیره شود.

مثلاً با ایندکس هش روی ایمیل:

buckets[hash("[email protected]")] -> [ptr to page 1]
buckets[hash("[email protected]")]   -> [ptr to page 2]

برخورد هش (hash collision) با linear probing مدیریت می‌شود. وقتی برخوردی رخ می‌دهد، پایگاه داده به‌سادگی bucket بعدی را بررسی می‌کند تا به جای خالی برسد. این یعنی در بدترین حالت جستجو می‌تواند به O(n) تنزل کند، اما با تابع هش خوب و load factor مناسب، معمولاً به O(1) می‌رسیم.

همین ساختار ایندکس هش را برای کوئری‌های تطبیق دقیق فوق‌العاده سریع می‌کند. فقط هش را حساب می‌کنید، به bucket می‌روید و اشاره‌گر را دنبال می‌کنید. اما همین ساختار آن را برای جستجوی بازه‌ای یا مرتب‌سازی بی‌فایده می‌کند، چون مقدارهای مشابه عمداً در bucketهای مختلف پخش می‌شوند.

استفاده در دنیای واقعی

با وجود سرعت در تطبیق دقیق، ایندکس هش در عمل نسبتاً کمیاب است. PostgreSQL از آن پشتیبانی می‌کند اما به‌طور پیش‌فرض استفاده‌اش نمی‌کند. چون B-Tree برای تطبیق دقیق تقریباً به همان اندازه خوب عمل می‌کند و علاوه بر آن کوئری بازه‌ای و مرتب‌سازی را هم پشتیبانی می‌کند. مستندات PostgreSQL هم می‌گوید B-Treeها مقایسه برابری را تقریباً به اندازه ایندکس هش کارآمد انجام می‌دهند.

با این حال، ایندکس هش در سناریوهای مشخص، به‌خصوص برای پایگاه‌های داده درون‌حافظه‌ای، می‌درخشد. مثلاً Redis از hash table به‌عنوان ساختار داده اصلی‌اش برای جستجوی کلید-مقدار استفاده می‌کند، چون همه داده در حافظه است. موتور ذخیره‌سازی MEMORY در MySQL ایندکس هش را پیش‌فرض می‌گذاشت، چون کوئری تطبیق دقیق درون‌حافظه‌ای کاربرد اصلی‌اش بود. در ذخیره‌سازی مبتنی بر دیسک، B-Tree معمولاً انتخاب بهتری است، چون الگوهای I/O دیسک را کارآمد مدیریت می‌کند.

چه زمانی ایندکس هش انتخاب کنیم

در مصاحبه‌های طراحی سیستم ممکن است در این موارد ایندکس هش را در نظر بگیرید.

• سریع‌ترین جستجوی دقیق ممکن را می‌خواهید.
• هرگز به کوئری بازه‌ای یا مرتب‌سازی نیاز نخواهید داشت.
• حافظه زیادی دارید (ایندکس هش از B-Tree بزرگ‌تر است).

اما در بیشتر موارد B-Tree انتخاب بهتری است. برای تطبیق دقیق تقریباً به همان سرعت است و اگر بعداً به کوئری بازه‌ای نیاز داشتید، انعطاف آن را دارید. بروس مومجیان، متخصص پایگاه داده، معتقد است ایندکس هش مسئله‌ای را حل می‌کند که ما به‌ندرت داریم.

در مصاحبه زیاد روی ایندکس هش تأکید نکنید. دانستن آن خوب است، اما تمرکز زیاد روی آن ممکن است شما را از رویه‌های واقعی پایگاه داده دور نشان دهد. یادتان باشد ایندکس هش به‌ندرت در سیستم‌های production استفاده می‌شود. کمی شبیه ابزار تخصصی آشپزخانه است که می‌خرید و فقط یک بار استفاده می‌کنید. B-Tree آن‌قدر همه‌کاره است که بیشتر مواردی را که ممکن است ایندکس هش در نظر بگیرید پوشش می‌دهد.

ایندکس‌های جغرافیایی

این‌جا نکته جالبی در مصاحبه‌های طراحی سیستم هست. ایندکس‌های جغرافیایی در عمل کاملاً تخصصی‌اند و ممکن است هیچ‌وقت سراغشان نروید، مگر با داده مکان کار کنید. اما به موضوع رایج مصاحبه‌ها تبدیل شده‌اند. دلیلش؟ ظهور سرویس‌های مبتنی بر مکان مثل Uber، Yelp و Find My Friends باعث شده جستجوی مجاورت (proximity search) موضوع محبوب مصاحبه شود.

چالش داده مکانی

فرض کنید اپلیکیشن کشف رستوران مثل Yelp می‌سازیم. میلیون‌ها رستوران در پایگاه داده داریم که هرکدام طول و عرض جغرافیایی دارند. کاربر اپلیکیشن را باز می‌کند و می‌خواهد «رستوران‌های نزدیک‌تر از ۵ مایل به من» را پیدا کند. به اندازه کافی ساده به نظر می‌رسد، درست است؟

رویکرد ساده‌لوحانه استفاده از ایندکس‌های B-Tree استاندارد روی طول و عرض جغرافیایی است:

CREATE TABLE restaurants (
    id SERIAL PRIMARY KEY,
    name VARCHAR(255),
    latitude DECIMAL(10, 8),
    longitude DECIMAL(11, 8)
);

CREATE INDEX idx_lat ON restaurants(latitude);
CREATE INDEX idx_lng ON restaurants(longitude);

اما وقتی بخواهیم جستجوی مجاورت اجرا کنیم، این رویکرد خیلی زود از هم می‌پاشد. فکر کنید ایندکس B-Tree روی طول و عرض جغرافیایی چطور عمل می‌کند. در اصل می‌خواهیم مسئله‌ای دوبعدی (پیدا کردن نقطه‌ها داخل یک دایره) را با دو ایندکس یک‌بعدی جدا حل کنیم.

وقتی «رستوران‌های نزدیک‌تر از ۵ مایل» را کوئری می‌کنیم، ناگزیر به یکی از دو مشکل کارایی می‌خوریم.

• اگر اول از ایندکس عرض جغرافیایی استفاده کنیم، همه رستوران‌های داخل بازه عرض مناسب را پیدا می‌کنیم. اما این یک نوار طولانی است که کل کره زمین را در آن عرض جغرافیایی پوشش می‌دهد! بعد برای هر کدام از آن رستوران‌ها باید بررسی کنیم که در بازه طول جغرافیایی مناسب هم هست یا نه. ایندکس طول جغرافیایی کمکی نمی‌کند، چون اسکن بازه‌ای نمی‌کنیم و برای هر رستورانی که در بازه عرض پیدا کردیم، جستجوی نقطه‌ای انجام می‌دهیم.
• اگر زرنگی کنیم و هر دو ایندکس را با هم استفاده کنیم (از طریق index intersection)، پایگاه داده باز هم باید دو مجموعه بزرگ نتیجه را ادغام کند: همه رستوران‌های داخل بازه عرض مناسب و همه رستوران‌های داخل بازه طول مناسب. این یک ناحیه جستجوی مستطیلی بسیار بزرگ‌تر از شعاع دایره‌ای واقعی ما می‌سازد و هنوز باید نتیجه‌های خیلی دور را فیلتر کنیم.

برای همین به ایندکس‌هایی نیاز داریم که روابط فضایی دوبعدی را بفهمند. به‌جای این‌که طول و عرض جغرافیایی را ابعاد مستقل بدانیم، ایندکس‌های فضایی اجازه می‌دهند نقطه‌ها را بر اساس نزدیکی واقعی‌شان در فضای دوبعدی سازمان‌دهی کنیم.

رویکردهای اصلی

سه رویکرد اصلی هست که در مصاحبه‌ها می‌بینید: geohash، quadtree و R-tree. هرکدام نقاط قوت و مصالحه‌های خودش را دارد، اما همه مشکل اساسی ما را حل می‌کنند: روابط فضایی را در ساختار ایندکس حفظ می‌کنند.

هر سه را بررسی می‌کنیم، اما یادتان باشد که با وجود تخصصی به نظر رسیدن این دانش، مصاحبه‌گرها عمدتاً می‌خواهند ببینند مسئله اصلی (چرا ایندکس‌های معمولی کم می‌آورند) را می‌فهمید و می‌توانید دست‌کم درباره یک راه‌حل استدلال کنید. مگر برای نقشی مصاحبه بدهید که مشخصاً با داده مکان کار می‌کند، به تخصص عمیق در هر سه رویکرد نیاز ندارید.

Geohash

با geohash شروع می‌کنیم. فهمیدن و پیاده‌سازی آن از همه ساده‌تر است و برای همین در بسیاری از پایگاه‌های داده انتخاب پیش‌فرض است. ایده اصلی زیبا و ساده است: یک مکان دوبعدی را طوری به رشته یک‌بعدی تبدیل کن که مجاورت حفظ شود.

تصور کنید دنیا را به چهار مربع تقسیم کنید و آن‌ها را از ۰ تا ۳ برچسب بزنید. بعد هر کدام از آن مربع‌ها را به چهار مربع کوچک‌تر تقسیم کنید و همین‌طور ادامه دهید. هر تقسیم دقت بیشتری به توصیف مکان ما اضافه می‌کند. geohash در اصل همین فرایند است، اما با رمزگذاری base32 که رشته‌هایی مثل dr5ru برای مکان‌ها می‌سازد. هرچه رشته بلندتر باشد، مکان دقیق‌تر است.

• dr ممکن است نماینده یک منطقه بسیار وسیع باشد.
• dr5 آن را به ناحیه کوچک‌تری محدود می‌کند.
• dr5ru ممکن است یک بلوک مشخص شهری را تعیین کند.

چیزی که geohash را هوشمندانه می‌کند این است که مکان‌های نزدیک به هم معمولاً رشته‌هایی با پیشوند مشابه دارند. دو رستوران در یک بلوک ممکن است geohash هایی داشته باشند که با dr5ru شروع می‌شوند، در حالی که رستورانی در محله دیگر ممکن است با dr5rv شروع شود.

ظرافت واقعی اینجاست. وقتی مکان‌های دوبعدی را به این رشته‌های مرتب تبدیل کردیم، می‌توانیم برای کوئری‌های فضایی از یک ایندکس B-Tree معمولی استفاده کنیم. یادتان هست B-Tree در تطبیق پیشوند و جستجوی بازه‌ای عالی است؟ دقیقاً همین را برای جستجوی مجاورت لازم داریم. وقتی رشته‌های geohash را با B-Tree ایندکس می‌کنیم:

CREATE INDEX idx_geohash ON restaurants(geohash);

پیدا کردن مکان‌های نزدیک به‌سادگی پیدا کردن رشته‌هایی با پیشوند منطبق است. اگر دنبال رستوران‌های نزدیک geohash با مقدار dr5ru هستیم، می‌توانیم در B-Tree بین dr5ru و dr5ru~ (که ~ بالاترین کاراکتر ممکن است) اسکن کنیم. این کار اجازه می‌دهد از تمام بهینه‌سازی‌هایی که پایگاه‌های داده از قبل برای B-Tree دارند استفاده کنیم، بدون نیاز به ساختار داده فضایی خاص.

برای همین دستورهای جغرافیایی Redis در پشت صحنه از همین رویکرد استفاده می‌کنند. وقتی اجرا می‌کنید:

GEOADD restaurants -122.4194 37.7749 "Restaurant A"
GEORADIUS restaurants -122.4194 37.7749 5 mi

Redis در پشت صحنه از geohash استفاده می‌کند تا نقطه‌های نزدیک را کارآمد پیدا کند. MongoDB هم از ایندکس‌های مبتنی بر geohash پشتیبانی می‌کند، هرچند جزئیاتش را پنهان می‌کند.

محدودیت اصلی geohash این است که مکان‌هایی که در واقعیت نزدیک به هم‌اند، اگر اتفاقاً دو طرف مرز یک خانه اصلی شبکه قرار بگیرند، ممکن است پیشوند مشابه نداشته باشند. مثل دو رستوران در دو طرف خیابانی که مرز geohash را تعیین می‌کند. اما در بیشتر کاربردها این حالت لبه‌ای آن‌قدر مهم نیست.

این ظرافت، یعنی تبدیل مسئله پیچیده دوبعدی به تطبیق پیشوند ساده رشته‌ای که می‌تواند از پیاده‌سازی‌های موجود B-Tree استفاده کند، دلیل محبوب بودن geohash است. فهمیدن و پیاده‌سازی آن آسان است و با سیستم‌های پایگاه داده موجود که از قبل می‌دانند رشته‌ها را کارآمد مدیریت کنند کار می‌کند.

Quadtree

هرچند امروز در پایگاه‌های داده production کمتر رایج است، quadtree رویکرد درختی بنیادینی برای ایندکس کردن فضای دوبعدی است که تفکر ما را درباره ایندکس فضایی شکل داده است. برخلاف geohash که مختصات را به رشته تبدیل می‌کند، quadtree فضا را مستقیماً با تقسیم بازگشتی ناحیه‌ها به چهار ربع تقسیم‌بندی می‌کند.

طرز کارش این است. با یک مربع شروع کنید که کل ناحیه شما را می‌پوشاند. وقتی مربعی بیش از آستانه‌ای نقطه داشت (معمولاً ۴ تا ۸)، آن را به چهار ربع مساوی تقسیم کنید. این تقسیم بازگشتی را ادامه دهید تا به حداکثر عمق برسید یا چگالی نقطه موردنظر در هر گره حاصل شود.

┌────┬────┐
│    │ C  │
│ A  ├──┬─┤
│    │B │D│
├────┼──┴─┤
│    │    │
│ E  │ F  │
│    │    │
└────┴────┘

این پارتیشن‌بندی فضایی به یک ساختار درختی نگاشت می‌شود.

برای جستجوی مجاورت، درخت را پایین می‌روید تا ربع هدف را پیدا کنید، ربع‌های همسایه در همان سطح را بررسی می‌کنید و در صورت نیاز با بالا یا پایین رفتن بین سطوح درخت شعاع جستجو را تنظیم می‌کنید.

مزیت اصلی quadtree وضوح تطبیقی (adaptive resolution) آن است. ناحیه‌های متراکم ریزتر تقسیم می‌شوند و ناحیه‌های کم‌تراکم ربع‌های بزرگ‌تر می‌مانند. اما برخلاف geohash که از پیاده‌سازی‌های موجود B-Tree استفاده می‌کند، quadtree به ساختارهای درختی تخصصی نیاز دارد. این پیچیدگی پیاده‌سازی دلیل این است که بیشتر پایگاه‌های داده مدرن گونه‌های geohash یا R-tree را ترجیح می‌دهند.

پس هرچند امروز در production رایج نیستند، quadtreeها اثر قابل‌توجهی بر ایندکس‌گذاری فضایی مدرن داشته‌اند. ایده اصلی تقسیم‌بندی فضایی بازگشتی پایه R-treeهاست که این ایده‌ها را برای ذخیره‌سازی مبتنی بر دیسک و مدیریت بهتر ناحیه‌های هم‌پوشان بهینه می‌کنند. اصول quadtree را حتی در سیستم‌های نقشه‌برداری مدرن می‌بینید. Google Maps از ساختار مشابهی برای سازمان‌دهی کاشی‌های نقشه در سطوح مختلف زوم استفاده می‌کند.

حالا ببینیم R-treeها چطور این مفاهیم را به استاندارد امروز production برای ایندکس فضایی تبدیل کردند.

R-Tree

R-treeها به ایندکس فضایی پیش‌فرض در پایگاه‌های داده مدرن مثل PostgreSQL/PostGIS و MySQL تبدیل شده‌اند. هم quadtree و هم R-tree داده مکانی را سلسله‌مراتبی سازمان‌دهی می‌کنند، اما R-tree رویکرد اساساً متفاوتی برای تقسیم فضا دارد.

R-tree به‌جای تقسیم فضا به ربع‌های ثابت، با مستطیل‌های انعطاف‌پذیر و هم‌پوشان کار می‌کند. quadtree هر ناحیه را بدون توجه به توزیع داده به چهار قسمت مساوی تقسیم می‌کند، اما R-tree مستطیل‌هایش را با داده واقعی تطبیق می‌دهد. سازمان‌دهی عکس‌ها روی یک میز را فکر کنید. رویکرد quadtree میز را به چهار قسمت مساوی تقسیم می‌کند و همین‌طور ادامه می‌دهد. اما R-tree اجازه می‌دهد دور عکس‌ها گروه‌های طبیعی و هم‌پوشان بسازید.

وقتی دنبال رستوران‌های اطراف در سان‌فرانسیسکو می‌گردید، R-tree ممکن است اول مستطیل بزرگی را که شهر را شامل می‌شود پیدا کند، بعد مستطیل‌های کوچک‌تر و هم‌پوشان را بررسی کند تا به مکان رستوران‌های مشخص برسد. این مستطیل‌ها محدود به اندازه یا موقعیت ثابت نیستند و با هر جایی که داده‌های شما واقعاً خوشه می‌شوند سازگار می‌شوند. در مقابل، quadtree شما را مجبور می‌کند در شبکه‌ای سخت از مربع‌های کوچک‌تر حرکت کنید که ممکن است برای رسیدن به همان مقصدها مرحله‌های بیشتری نیاز داشته باشد.

این انعطاف مزیت حیاتی‌ای دارد: R-treeها می‌توانند نقطه‌ها و شکل‌های بزرگ‌تر را هر دو در یک ساختار ایندکس به‌طور کارآمد مدیریت کنند. R-tree می‌تواند همه‌چیز را از مکان رستوران‌های مجزا گرفته تا چندضلعی منطقه تحویل و شبکه جاده‌ها ایندکس کند. مستطیل‌ها اندازه‌شان را تنظیم می‌کنند تا هر شکلی که درون‌شان است را محدود کنند. quadtree با این داده‌های ترکیبی مشکل دارد. تقسیم‌بندی را ادامه می‌دهد تا بتواند هر شکل را جدا کند و نتیجه‌اش درخت عمیق‌تر و پیمایش پیچیده‌تر است.

مصالحه این انعطاف این است که مستطیل‌های هم‌پوشان گاهی ما را مجبور می‌کنند چند شاخه درخت را جستجو کنیم. پیاده‌سازی‌های مدرن R-tree از الگوریتم‌های هوشمند استفاده می‌کنند تا این هم‌پوشانی را با عمق درخت متعادل کنند و نحوه خواندن داده از دیسک را تنظیم کنند. همین تعادل بین انعطاف و کارایی دیسک دلیل این است که R-tree انتخاب استاندارد برای ایندکس فضایی در production شده است.

اگر در مصاحبه درباره ایندکس‌گذاری جغرافیایی از شما پرسیدند، روی توضیح روشن مسئله تمرکز کنید و رویکرد درختی را با رویکرد مبتنی بر هش مقایسه کنید. مثلاً می‌توانید چیزی شبیه این بگویید:

«ایندکس‌های سنتی مثل B-Tree برای داده مکانی خوب کار نمی‌کنند، چون طول و عرض جغرافیایی را ابعاد مستقل می‌بینند. برای جستجوی کارآمد مکان‌های نزدیک، به ایندکسی نیاز داریم که روابط فضایی را بفهمد. Geohash رویکردی مبتنی بر هش است که مختصات دوبعدی را به رشته یک‌بعدی تبدیل می‌کند و اجازه می‌دهد برای جستجوی مجاورت از ایندکس B-Tree معمولی روی رشته‌ها استفاده کنیم. اما رویکردهای درختی مثل R-tree با گروه‌بندی اشیای نزدیک در مستطیل‌های هم‌پوشان و ساختن سلسله‌مراتبی از bounding boxها می‌توانند انعطاف و دقت بیشتری بدهند.»

با مقایسه این دو رویکرد، درک عمیق‌تری از مصالحه‌های ایندکس‌گذاری جغرافیایی نشان می‌دهید.

ایندکس معکوس (Inverted Index)

B-Treeها در پیدا کردن تطبیق دقیق و بازه‌ها عالی هستند، اما وقتی باید در محتوای متنی جستجو کنیم کم می‌آورند. کوئری‌ای مثل این را در نظر بگیرید:

SELECT * FROM posts WHERE content LIKE '%database%';

اینجا دنبال پست‌هایی هستیم که کلمه «database» در هر جای محتوایشان باشد، نه فقط پست‌هایی که با آن شروع یا تمام می‌شوند. حتی با ایندکس B-Tree روی ستون محتوا، پایگاه داده به هیچ‌وجه نمی‌تواند از ایندکس استفاده کند. چرا؟ ایندکس B-Tree فقط به تطبیق پیشوندی (مثل database%) یا تطبیق پسوندی (اگر محتوای معکوس‌شده را ایندکس کنید) کمک می‌کند. وقتی الگو می‌تواند هر جای متن باشد، پایگاه داده چاره‌ای جز بررسی همه کاراکترهای هر پست ندارد و باید همه فیلدهای متنی را در حافظه بخواند تا تطبیق پیدا کند.

این تطبیق الگوی کامل، با رشد محتوای متنی، به‌شکل نمایی کندتر می‌شود. هر کاراکتر اضافه در پست‌ها یعنی داده بیشتر برای اسکن، حافظه بیشتر برای مصرف و چرخه‌های CPU بیشتر برای بررسی الگوها. مثل این است که بخواهید با خواندن صفحه‌به‌صفحه همه کتاب‌ها، یک کلمه را در کل کتابخانه پیدا کنید.

ایندکس معکوس با وارونه کردن رابطه بین سندها و محتوایشان این مشکل را حل می‌کند. به‌جای ذخیره سندها همراه کلمه‌هایشان، کلمه‌ها را همراه سندهایشان ذخیره می‌کند. مثل ایندکس پشت کتاب درسی است. به‌جای خواندن همه صفحه‌ها برای پیدا کردن اشاره به «ویژگی‌های ACID»، «ACID» را در ایندکس پیدا می‌کنید و هر صفحه‌ای را که درباره‌اش بحث می‌کند می‌بینید.

طرز کار آن این‌طور است. پلتفرم ساده وبلاگ‌نویسی را با این پست‌ها در نظر بگیرید:

doc1: "B-trees are fast and reliable"
doc2: "Hash tables are fast but limited"
doc3: "B-trees handle range queries well"

ایندکس معکوس این نگاشت را می‌سازد:

b-trees  -> [doc1, doc3]
fast     -> [doc1, doc2]
reliable -> [doc1]
hash     -> [doc2]
tables   -> [doc2]
limited  -> [doc2]
handle   -> [doc3]
range    -> [doc3]
queries  -> [doc3]

این نگاشت پایه مفهوم اصلی را نشان می‌دهد، اما ایندکس‌های معکوس production خیلی پیچیده‌ترند. وقتی سیستمی مثل Elasticsearch متن را ایندکس می‌کند، اول آن را از یک خط لوله تحلیل (analysis pipeline) رد می‌کند که محتوا را پردازش و غنی می‌کند. این یعنی:

• شکستن متن به توکن (کلمه یا زیرکلمه).
• تبدیل به حروف کوچک.
• حذف کلمه‌های توقف (stop word) رایج مثل «the» یا «and».
• اغلب اعمال stemming (تبدیل کلمه‌ها به شکل ریشه).

پس وقتی کاربر «databases» را جستجو می‌کند، سیستم می‌تواند سندهایی را که «database»، «databases» یا حتی «databasing» دارند تطبیق دهد. برای همین جستجوی متن کامل در مقایسه با تطبیق الگوی سخت‌گیرانه حس طبیعی‌تری دارد.

سیستم‌های جستجوی مدرن مثل Elasticsearch و Lucene قابلیت‌های اضافه‌ای روی این پایه می‌سازند.

• تحلیل بسامد اصطلاح (term frequency)، یعنی هر کلمه چند بار ظاهر می‌شود.
• امتیازدهی ارتباط (relevance scoring)، یعنی کدام سندها بهتر با کوئری می‌خوانند.
• تطبیق فازی (fuzzy matching)، یعنی پیدا کردن مواردی مثل «databse» که غلط املایی دارند.
• کوئری عبارتی (phrase query)، یعنی تطبیق دنباله دقیق کلمه‌ها.

در عمل هر جا جستجوی متنی پیشرفته لازم باشد، ایندکس معکوس را می‌بینید. وقتی توسعه‌دهندها مخزن‌های GitHub را جستجو می‌کنند، وقتی کاربران در تاریخچه پیام Slack جستجو می‌کنند، یا وقتی در اسناد جستجو می‌کنید، همه این‌ها در پشت صحنه از ایندکس معکوس استفاده می‌کنند.

البته مصالحه‌هایی هم هست. ایندکس معکوس سربار ذخیره‌سازی قابل‌توجهی دارد و به‌روزرسانی‌اش باید با دقت انجام شود. وقتی سندی تغییر می‌کند، باید ورودی هر اصطلاح را به‌روز کنید. اما برای این‌که متن واقعاً قابل‌جستجو شود، این مصالحه‌هایی است که حاضریم بپذیریم.

درباره نحوه کار ایندکس معکوس در بررسی عمیق Elasticsearch بیشتر بخوانید.

الگوهای بهینه‌سازی ایندکس

تا اینجا انواع اصلی ایندکس‌هایی را بررسی کردیم که در مصاحبه‌های طراحی سیستم می‌بینید: B-Tree برای کوئری همه‌منظوره، ایندکس هش برای تطبیق دقیق، ایندکس مکانی برای داده مکان، و ایندکس معکوس برای جستجوی متن. هر نوع یک دسته مشخص از مسائل را با مصالحه در ذخیره‌سازی، کارایی و انعطاف حل می‌کند.

مهندسان باتجربه زمان قابل‌توجهی صرف تحلیل الگوهای خواندن و نوشتن اپلیکیشنشان می‌کنند و دنبال راه‌هایی برای کم کردن هزینه پردازش کوئری‌های رایج می‌گردند. با بررسی query plan و متریک‌های پایگاه داده، گلوگاه‌های کارایی را شناسایی می‌کنند و بعد با استراتژی‌های مناسب ایندکس‌گذاری کارایی را راهبردی بهتر می‌کنند. این اغلب یعنی فراتر از انتخاب نوع مناسب ایندکس نگاه کنید. موضوع فهمیدن الگوهای دسترسی و ساختن رویکرد ایندکس‌گذاری‌ای است که از آن‌ها به‌خوبی پشتیبانی کند.

ایندکس ترکیبی (Composite Index)

ایندکس ترکیبی رایج‌ترین الگوی بهینه‌سازی‌ای است که در عمل می‌بینید. به‌جای ساختن ایندکس جدا برای هر ستون، یک ایندکس واحد می‌سازیم که چند ستون را با ترتیب مشخص ترکیب می‌کند. این با نحوه کوئری زدن داده در برنامه‌های واقعی هم‌خوان است.

کوئری معمول فید شبکه اجتماعی را در نظر بگیرید:

SELECT * FROM posts
WHERE user_id = 123
AND created_at > '2024-01-01'
ORDER BY created_at DESC;

می‌توانیم دو ایندکس جدا بسازیم:

CREATE INDEX idx_user ON posts(user_id);
CREATE INDEX idx_time ON posts(created_at);

اما این بهینه نیست. پایگاه داده باید:

1. از یک ایندکس برای پیدا کردن همه پست‌های کاربر ۱۲۳ استفاده کند.
2. از ایندکس دیگر برای پیدا کردن همه پست‌های بعد از اول ژانویه استفاده کند.
3. اشتراک این نتایج را بگیرد.
4. نتیجه نهایی را بر اساس created_at مرتب کند.

در عوض یک ایندکس ترکیبی همه چیزی را که لازم داریم یک‌جا می‌دهد:

CREATE INDEX idx_user_time ON posts(user_id, created_at);

وقتی ایندکس ترکیبی می‌سازیم، در واقع B-Treeای می‌سازیم که کلید هر گره در آن ترکیبی از ستون‌های ایندکس‌شده است. برای ایندکس (user_id, created_at) هر کلید در B-Tree عملاً یک tuple از هر دو مقدار است. B-Tree این کلیدها را اول بر اساس user_id و بعد بر اساس created_at مرتب نگه می‌دارد. از نظر مفهومی کلیدها شبیه این هستند:

(1, 2024-01-01)
(1, 2024-01-02)
(1, 2024-01-03)
(2, 2024-01-01)
(2, 2024-01-02)
(3, 2024-01-01)

حالا وقتی کوئری را اجرا می‌کنیم، پایگاه داده می‌تواند B-Tree را پیمایش کند تا اولین ورودی user_id=123 را پیدا کند، بعد ورودی‌های ایندکس آن کاربر را به‌ترتیب اسکن کند تا به ورودی‌ای برسد که از بازه تاریخ ما بیرون است. چون ورودی‌ها در هر گروه user_id از قبل بر اساس created_at مرتب شده‌اند، فیلتر و مرتب‌سازی را رایگان می‌گیریم.

این ساختار به‌خصوص کارآمد است، چون از ترتیب طبیعی B-Tree برای مدیریت چند شرط در یک پیمایش ایندکس استفاده می‌کنیم. کوئری دوبعدی خود (کاربر و زمان) را عملاً از طریق ورودی‌های مرتب ایندکس به یک اسکن یک‌بعدی تبدیل کرده‌ایم.

ترتیب مهم است

ترتیب ستون‌ها در ایندکس ترکیبی بسیار مهم است. ایندکس ما روی (user_id, created_at) برای کوئری‌هایی که اول روی user_id فیلتر می‌کنند عالی است، اما برای کوئری‌هایی که فقط روی created_at فیلتر می‌کنند فایده‌ای ندارد. این از نحوه کار B-Tree می‌آید. فقط می‌توانیم از ایندکس برای پیشوندهای فهرست ستون‌هایمان کارآمد استفاده کنیم.

برای همین اغلب می‌شنوید که متخصصان پایگاه داده می‌گویند «ستون‌ها را از انتخابی‌ترین (selective) به کم‌انتخابی‌ترین ترتیب بدهید». اما در عمل ظرافت‌های بیشتری هست. گاهی الگوهای کوئری بر انتخابی بودن می‌چربند. اگر مرتب بر اساس ستون مشخصی مرتب‌سازی می‌کنید، قرار دادن آن در ایندکس ترکیبی (حتی اگر خیلی انتخابی نباشد) می‌تواند عملیات مرتب‌سازی پرهزینه را حذف کند.

سناریوهای رایج مصاحبه:

• جستجوی تاریخچه سفارش: (customer_id, order_date)
• پردازش رویداد: (status, priority, created_at)
• فید فعالیت: (user_id, type, timestamp)

ایندکس پوششی (Covering Index)

ایندکس پوششی همه ستون‌های موردنیاز کوئری را شامل می‌شود، نه فقط ستون‌هایی که روی آن‌ها فیلتر یا مرتب‌سازی می‌کنید. نمایش فید شبکه اجتماعی را با زمان پست و تعداد لایک فکر کنید. با ایندکس معمولی روی (user_id, created_at)، پایگاه داده اول پست‌های منطبق را در ایندکس پیدا می‌کند و بعد باید صفحه کامل داده هر پست را بخواند تا تعداد لایک را بگیرد. این مقدار زیادی خواندن اضافه از دیسک فقط برای نمایش یک عدد است.

با قرار دادن ستون لایک مستقیم در ایندکس، می‌توانیم جستجوی گران صفحه را کامل کنار بگذاریم. پایگاه داده می‌تواند هر چه لازم داریم را مستقیم از خود ایندکس برگرداند:

CREATE TABLE posts (
    id SERIAL PRIMARY KEY,
    user_id INT,
    title TEXT,
    content TEXT,
    likes INT,
    created_at TIMESTAMP
);

-- Regular index
CREATE INDEX idx_user_time ON posts(user_id, created_at);

-- Covering index includes likes column
CREATE INDEX idx_user_time_likes ON posts(user_id, created_at) INCLUDE (likes);

من SQL را برای مثال استفاده می‌کنم، چون فراگیرترین زبان برای کار با پایگاه داده است. اما همین اصول درباره سیستم‌های پایگاه داده دیگر و حتی راه‌حل‌های NoSQL هم صدق می‌کند.

با ایندکس پوششی، PostgreSQL می‌تواند نتیجه‌ها را فقط از داده‌های ایندکس برگرداند و لازم نیست هر پست را در جدول اصلی پیدا کند. این برای کوئری‌هایی که فقط به زیرمجموعه کوچکی از ستون‌های جدول‌های بزرگ نیاز دارند به‌خصوص قدرتمند است.

البته مصالحه در اندازه است. ایندکس‌های پوششی بزرگ‌ترند، چون ستون‌های اضافه را ذخیره می‌کنند. اما برای کوئری‌های پرتکراری که فقط چند ستون می‌خواهند، بهبود کارایی ناشی از پرهیز از جستجوی جدول اغلب هزینه ذخیره‌سازی را توجیه می‌کند. این به‌خصوص برای فیدهای اجتماعی، لیدربوردها و قابلیت‌های خواندن‌سنگین دیگر که سرعت کوئری بسیار مهم است صدق می‌کند.

واقعیت در سال ۲۰۲۵ این است که ایندکس پوششی بیشتر یک بهینه‌سازی خاص است تا راه‌حل عمومی. بهینه‌ساز کوئری (query optimizer) پایگاه‌های داده مدرن در اجرای کارآمد کوئری با ایندکس‌های معمولی خیلی هوشمند شده است. ایندکس‌های پوششی در سناریوهای خاص، مثل جدول‌های خواندن‌سنگین با ستون‌های محدود، می‌توانند کارایی قابل‌توجهی بدهند. اما هزینه‌های واقعی از نظر سربار نگهداری و فضای ذخیره‌سازی دارند.

در مصاحبه ممکن است عاقلانه باشد روی استراتژی‌های ساده‌تر ایندکس‌گذاری تمرکز کنید، و اگر سراغ ایندکس پوششی می‌روید، مطمئن شوید دلیل خوبی برای لزوم آن دارید. اگر مطمئن نیستید در سناریوی مشخصی منطقی است یا نه، اغلب بهتر است به سمت سادگی خطا کنید.

جمع‌بندی

ایندکس‌ها نه‌فقط در مصاحبه، بلکه در سیستم‌های production هم مهم‌اند. دانستن نحوه استفاده مؤثر از آن‌ها مهارت کلیدی هر توسعه‌دهنده است و دانشی است که مرتب در مصاحبه‌ها سنجیده می‌شود.

از همه مهم‌تر این است که بدانید کی به ایندکس نیاز دارید و روی کدام ستون‌ها. وقتی schema جدید طراحی می‌کنید، این باید غریزه طبیعی‌تان باشد. به الگوهای کوئری‌ای که احتمالاً اجرا می‌کنید فکر کنید و این‌که آیا روی ستون‌های مشخصی فیلتر یا مرتب‌سازی می‌کنید.

از اینجا به بعد انتظار می‌رود از شما بپرسند برای سناریوی مشخصی چه نوع ایندکسی استفاده می‌کنید. وقتی شک دارید، سراغ B-Tree بروید. B-Tree چاقوی سوئیسی ایندکس‌هاست و هم تطبیق دقیق و هم کوئری بازه‌ای را کارآمد انجام می‌دهد و به همین دلیل خوب است که بیشتر پایگاه‌های داده آن را پیش‌فرض می‌گیرند.

دو استثنای اصلی وقتی است که با داده مکانی یا جستجوی متن کامل سروکار دارید.

اگر با طول و عرض جغرافیایی کار می‌کنید و باید نقطه‌های نزدیک را کارآمد جستجو کنید، باید ایندکس جغرافیایی انتخاب کنید. اگر می‌خواهید فقط یک گزینه را بدانید، geohash را یاد بگیرید. اگر بتوانید توضیح دهید چطور کار می‌کند و مصالحه‌اش با رویکردهای درختی را بسنجید، بهتر هم هست.

در نهایت، وقتی نوبت جستجوی متن کامل می‌رسد، برای جستجوی کارآمد در حجم زیاد متن به ایندکس معکوس نیاز دارید. بعید است عمیقاً درباره نحوه کارش پرسیده شوید، اما باید درک پایه‌ای از نگاشت معکوس کلمه‌های کلیدی به سندها داشته باشید.

با داشتن این ابزارها در جعبه‌ابزارتان، برای اکثریت قریب‌به‌اتفاق سوال‌های ایندکس‌گذاری که ممکن است پیش بیاید آماده خواهید بود.