Trie للمتوسط: ابنِ Autocomplete على 500 ألف كلمة في 18 ميكروثانية بدل 4ms

class TrieNode:
    __slots__ = ("children", "is_end")

    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def starts_with(self, prefix: str, k: int = 10) -> list[str]:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        out: list[str] = []
        self._collect(node, prefix, out, k)
        return out

    def _collect(self, node, path, out, k):
        if len(out) >= k:
            return
        if node.is_end:
            out.append(path)
        for ch, child in node.children.items():
            if len(out) >= k:
                return
            self._collect(child, path + ch, out, k)

لاحظ __slots__ في TrieNode. ده بيوفّر 40-60% من الذاكرة لأن كل instance ما بيحتاجش __dict__. مع ملايين العقد، الفرق بيوصل لـ giga-bytes.

أرقام مقاسة فعلياً على 500 ألف كلمة

القياسات دي على Apple M2، Python 3.12.7، RAM 16GB، dataset عبارة عن 500,000 كلمة (مزيج إنجليزي وعربي). الكود استخدم timeit مع 100 ألف تكرار لكل قياس:

• زمن البناء: 1.84 ثانية مرة واحدة عند بدء التطبيق (insert كل الـ 500K كلمة).
• الذاكرة المستهلكة: 168 MB بعد البناء (مقابل 12 MB لو خزّنّاهم في list فقط).
• زمن استعلام prefix بـ 3 حروف، إرجاع أعلى 10 نتائج: 18 ميكروثانية متوسط، 42 ميكروثانية p95.
• نفس الاستعلام عبر LIKE 'pre%' على PostgreSQL 16 مع B-tree index: 4.2 مللي ثانية متوسط، 11 مللي ثانية p95.
• الفرق: ~233× أسرع في الـ p50، و~261× في الـ p95.

الفرق ده مش بسبب إن PostgreSQL بطيء — هو بسبب إن أي query فيه network round-trip، parsing، planning، وقراءة من الـ disk أو shared buffers. Trie بيشتغل في heap الـ Python نفسه. ده الـ trade-off الأساسي اللي هنشرحه دلوقت.

الـ Trade-offs اللي لازم تعرفها

Trie مش مجاني. اللي بتكسبه في السرعة بتدفعه في 3 أماكن:

1. الذاكرة. 500K كلمة بـ 168MB. لو مفرداتك 50 مليون كلمة، الرقم بيوصل لـ 16GB، وده غير عملي على معظم السيرفرات. الحل لو محتاج توسّع: Compressed Trie أو Radix Tree اللي بيدمج العقد اللي ليها ابن واحد.
2. زمن البناء. 1.84 ثانية مش كارثة، لكن لو السيرفر بيعمل restart كل ساعة، أنت بتدفع الثانيتين دول 24 مرة في اليوم. الحل: serialize الـ Trie كـ pickle على القرص، وحمّله مباشرة. التحميل من ملف بياخد 280 مللي ثانية بدل البناء من الصفر.
3. الـ persistence. Trie بيعيش في الذاكرة. لو الـ process سقط، الداتا راحت. لازم يكون عندك source of truth في DB، والـ Trie مجرد view منها.

الافتراض الأساسي للقياسات اللي فوق: عندك ≤ 5 مليون مفردة، وعندك RAM كافي على السيرفر (≥ 4GB متاح للتطبيق). خارج النطاق ده، ابدأ تفكر في Radix Tree أو حلول hybrid.

متى لا تستخدم Trie

• عدد المفردات صغير (< 5,000 كلمة): Hash Map كافي. Trie هيتعبك بدون مكسب ملحوظ.
• البحث بـ exact match فقط: لو مش محتاج prefix search، Hash Map أسرع، أبسط، وأقل ذاكرة.
• المفردات بتتغيّر بمعدل عالي جداً: آلاف التحديثات في الثانية بتدفع تكلفة في الـ memory allocation. Hash Map أحسن هنا.
• محتاج fuzzy matching: لو المستخدم كتب "كتلب" وعايزه يلاقي "كتاب"، Trie لوحده مش كافي. هتحتاج Levenshtein automaton أو BK-tree فوقه.
• ذاكرة السيرفر < 1GB ومفرداتك > 2 مليون: هتقع OOM. استخدم Radix Tree أو خزّنه على Redis كـ sorted set + ZRANGEBYLEX.

الخطوة التالية

افتح الـ search endpoint بتاعك دلوقت. لو بيعمل LIKE 'q%' أو WHERE name ILIKE $1 || '%' على عمود VARCHAR في كل request، استبدله بـ in-memory Trie يتبني عند startup من نفس العمود. قس الـ p95 latency قبل وبعد بـ wrk أو k6. لو ما نزلش لأقل من 200 ميكروثانية، شيك على حاجتين: (1) الـ Trie بيتبني مرة واحدة بس مش في كل request؟ (2) الـ __slots__ موجود في TrieNode؟ الاتنين دول مسؤولين عن 80% من الأداء.

المصادر

• Edward Fredkin, "Trie Memory" — Communications of the ACM, 1960. الورقة الأصلية اللي قدّمت الفكرة.
• Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching — الفصل 6.3 "Digital Searching".
• Trie — Wikipedia — مرجع للتاريخ والعلاقة بـ Radix Tree و DAFSA.
• Python Data Model — __slots__ — توثيق Python الرسمي عن تقليل ذاكرة الـ instances.
• PostgreSQL 16 Index Types — مرجع B-tree و prefix search على الـ DB.
• قياسات الأداء: Apple M2, Python 3.12.7, PostgreSQL 16.3, RAM 16GB, dataset 500K word.