بنناجح
المرحلة 1: الـ Index من جوه · الدرس 2 من 4 · 15 دقيقة

يعني إيه Index؟ وليه B+Tree؟

الـ Index نسخة مترتبة من عمود، جنب كل قيمة مكان صفها. والدرس ده بيوريك ليه الداتابيز اختارت الـ B+Tree بالذات، وإزاي 3 مستويات بتكفي لمليار صف.

في الدرس ده هتتعلم
  • تعرّف الـ Index وتعرف الـ 3 حقايق اللي لازم تفضل في دماغك
  • تفهم ليه مش Array ولا Hash Table ولا Binary Search Tree
  • تحسب عمق الـ B+Tree بالـ Fanout، وده سؤال إنترفيو مشهور

1. يعني إيه Index؟

فكرة الـ Index بسيطة: بتاخد عمود (زي email)، وتعمل منه نسخة مترتبة لوحدها، وجنب كل قيمة بتكتب مكان الصف في الجدول.

الـ Index مش نسخة من الجدول كله. هو بيخزّن العواميد اللي اتعمل عليها بس + المرجع. يعني Index على email في جدول فيه 30 عمود = جزء صغير من حجمه. بس لو عملت 10 Indexes، المساحة بتتجمع، وفي جداول كبيرة بنلاقي حجم الـ Indexes أكبر من الداتا نفسها.

وفيه 3 حقايق لازم تفضل في دماغك:

  1. الـ Index نسخة إضافية: بياخد مساحة، ولازم يتحدّث مع كل تعديل.
  2. الـ Index مترتب على حاجة معينة: Index مترتب بالإيميل مش هيساعدك تدوّر بالاسم.
  3. الـ Index بيوديك للمكان، والمكان لسه محتاج يتقري. إلا لو كل اللي محتاجه موجود في الـ Index نفسه، ودي اسمها Covering وهنشوفها بعدين.

2. ليه مش Array ولا Hash؟

ليه مانرتبش الإيميلات في Array ونعمل Binary Search؟ البحث هيبقى O(log N) فعلاً، بس كل INSERT في النص هيزحزح ملايين العناصر علشان يعمل مكان: O(N) لكل تسجيل جديد.

طيب Hash Table؟ ممتازة للتساوي = في O(1). بس الـ Hash ملهاش ترتيب: مش هتعرف > ولا BETWEEN ولا ORDER BY ولا LIKE 'omar%'، والداتابيز محتاجة الحاجات دي طول الوقت.

طيب Binary Search Tree؟ كل Node فيها مفتاح واحد، فـ 10 مليون مفتاح = حوالي 24 مستوى = 24 قراءة Disk عشوائية.

الهيكل البحث المشكلة مع الداتابيز
Array مترتب O(log N) INSERT في النص = O(N)
Hash Table O(1) للتساوي بس مفيش Range ولا ترتيب
Binary Search Tree O(log₂ N) ≈ 24 مستوى قراءة Disk لكل مستوى
B+Tree O(log₁₀₀₀ N) ≈ 3 مستويات ✓ مصممة للـ Disk

3. الـ B+Tree

الحل اسمه B-Tree، واخترعه Rudolf Bayer و Edward McCreight في معامل Boeing سنة 1970، واتنشر سنة 1972. ولحد النهارده هو الأساس في أغلب الداتابيز العلائقية.

الفكرة العبقرية: كل Node في الشجرة = Page كاملة. فبدل ما تتفرع لاتنين، بتتفرع لـ مئات. الرقم ده اسمه Fanout، وهو اللي بيخلّي الشجرة قصيرة جداً. ونسخة الداتابيز اسمها B+Tree، وفيها حاجتين زيادة:

  • الـ Nodes الداخلية فيها مفاتيح للتوجيه بس، والداتا الحقيقية في الأوراق (Leaves).
  • الأوراق مربوطة ببعض، فالـ Range Scan بيمشي على الأوراق من غير ما يرجع للـ Root.
دوّر في الـ B+Tree بنفسكجرّب بنفسك

اكتب أي رقم من 1 لـ 99 ودوس “دوّر”. بعدين جرّب “هات من 30 لـ 60” وشوف الـ Range Scan بيمشي على الأوراق المربوطة.

علّم عليه لما تقدر تجاوب أسئلة الإنترفيو من غير ما تبص.