لو endpoint الـ autocomplete عندك بياخد 1.8 ثانية لكل request على جدول products فيه 500 ألف اسم، المشكلة مش بطء PostgreSQL ولا الـ index. المشكلة إنك بتسأل DB سؤال مش مصمّم له: "هاتلي كل الكلمات اللي بتبدأ بـ 'lap'". Trie بيرد على نفس السؤال في 2 مللي ثانية بـ Python خام، بدون Redis ولا Elasticsearch.
المشكلة باختصار
الـ search box في تطبيقك المفروض يرجّع اقتراحات تحت 50ms علشان المستخدم يحس إن الواجهة بترد فوري. لو بتعمل query زي ده على كل keystroke:
SELECT name FROM products WHERE name LIKE 'lap%' LIMIT 10;
الـ B-tree index بيشتغل صح في الحالة دي (prefix match قابل للفهرسة)، بس لو الجدول 500 ألف صف وفيه 200 طلب/ثانية في وقت الذروة، الـ DB بتقعد تتنفّس. Connection pool بيتسد، الـ p99 latency بيوصل 2 ثانية، والمستخدم بيفقد ثقته في الـ search.
الحل اللي بيستخدمه فعلياً Google Search و T9 و routing tables في الـ kernel: هيكل بيانات اسمه Trie (شجرة prefix).
مثال للمبتدئ: دفتر تليفون مرتب
تخيّل دفتر تليفون قديم بأقسام بحرف الأبجدية. لو بتدوّر على رقم "أحمد ماهر"، أنت مش بتقلّب كل الصفحات. بتفتح قسم الألف، بعدين بتدوّر على الأسماء اللي بتبدأ بـ "أح"، بعدين "أحم"، وهكذا. كل خطوة بتلغي 90% من الصفحات الباقية.
Trie بيشتغل بنفس المنطق بالظبط. كل حرف بيكون عقدة في الشجرة. جذر الشجرة فاضي. تحته 28 فرع محتمل لكل حرف عربي (أو 26 للإنجليزي). كل فرع بيوصلك لجزء من الكلمات اللي بتبدأ بنفس البداية. لما تكتب "lap"، أنت بتمشي 3 خطوات في الشجرة فقط، وبتلاقي تحتك كل الكلمات اللي بتبدأ بـ "lap" مفصولة عن بقية مليون كلمة.
التعريف العلمي الدقيق
Trie (الاسم جاي من كلمة retrieval، اقترحه Edward Fredkin سنة 1960) هو k-ary tree كل عقدة فيها بتمثّل حرف واحد، والمسار من الجذر لأي عقدة بيمثّل prefix معيّن. كل عقدة فيها flag بيقول هل المسار اللي وصل لها يمثّل كلمة كاملة (terminal node) ولا مجرد prefix.
التعقيد الزمني للبحث عن أي كلمة طولها m هو O(m) — مش O(n) ولا O(log n). يعني سرعة البحث مستقلة تماماً عن عدد الكلمات في الشجرة. مليون كلمة أو ألف كلمة، لو الـ prefix طوله 4 أحرف، بتمشي 4 خطوات بس.
الفرق عن Hash Map
Hash Map بيرد O(1) للبحث عن كلمة كاملة، بس مش بيقدر يرد prefix*. لازم تمر على كل المفاتيح. Trie بيخسر ثابت زمني صغير (m خطوات بدل 1)، بس بيكسب القدرة على prefix queries — وده اللي محتاجه autocomplete.
