كان البحث عن أقرب سائق يستغرق دقيقة: كيف أنقذتنا ‘الأشجار الرباعية’ (Quadtrees) من جحيم الاستعلامات المكانية؟

يا جماعة الخير، السلام عليكم ورحمة الله.

اسمحوا لي أبدأ معكم بقصة صارت معي قبل كم سنة، قصة فيها سهر وتعب وقهوة كثير، بس نهايتها كانت حلوة وفيها درس مهم. كنا في فريق صغير، شغالين على تطبيق توصيل، زي التطبيقات المشهورة اليوم. وصلنا لمرحلة مهمة جدًا: ربط الزبون بأقرب سائق متوفر. في البداية، الأمور كانت بسيطة، عدد السائقين والطلبات قليل، وكل شي كان يمشي “زي الحلاوة”.

لكن مع نمو التطبيق، بدأت الكوابيس. وصلتني رسالة نصية الساعة 2 الفجر من مدير المشروع: “أبو عمر، الحقنا! التطبيق بطيء جدًا والناس بتشتكي!”. فتحت لوحة المراقبة وشفت الكارثة: استعلام البحث عن أقرب سائق كان يأخذ أحيانًا 60 ثانية كاملة! دقيقة كاملة عشان يلاقي سائق! تخيلوا شعور المستخدم وهو بستنى كل هالوقت. كان واضح إنه لو ما حلينا هاي المشكلة بسرعة، كل شغلنا وتعبنا راح يروح على الفاضي.

قضينا الليلة أنا والشباب نحلل المشكلة. كانت الطريقة اللي بنستخدمها ساذجة جدًا، أو زي ما بنحكي بالهندسة “Brute Force”. كنا ببساطة، لكل طلب جديد، بنمر على كل سائق متوفر في قاعدة البيانات، نحسب المسافة بينه وبين الزبون، ونختار الأقرب. طريقة منطقية، لكنها كارثية على نطاق واسع. بعد ليلة طويلة من البحث والنقاش وشرب ما لا يقل عن “دلة” قهوة، واحد من الشباب صاح: “يا جماعة، لازمنا Spatial Indexing!”. ومن هنا، بدأت رحلتنا مع المنقذ: الأشجار الرباعية.

ما هو الجحيم الذي كنا فيه؟ (مشكلة الاستعلام الخطي)

قبل ما نحكي عن الحل، خلوني أشرح لكم أكثر عن المشكلة الأساسية. الطريقة اللي كنا بنستخدمها اسمها “البحث الخطي” أو Linear Search. تخيل إنك مسؤول عن إيجاد أقرب سائق لزبون في مدينة فيها 10,000 سائق متوفر. اللي كنا بنعمله هو كالتالي:

1. استقبال إحداثيات الزبون (خط الطول والعرض).
2. جلب قائمة بكل السائقين المتوفرين من قاعدة البيانات (10,000 سائق).
3. المرور على القائمة سائقًا تلو الآخر (Loop).
4. في كل مرة، نحسب المسافة بين الزبون والسائق الحالي باستخدام معادلة مثل “هافرساين”.
5. نحتفظ بأقصر مسافة نجدها حتى الآن.
6. بعد المرور على الـ 10,000 سائق، نرجع السائق صاحب أقصر مسافة.

هذا الأسلوب له تعقيد زمني يُعرف بـ O(n)، حيث n هو عدد السائقين. يعني لو زاد عدد السائقين لـ 20,000، الوقت راح يتضاعف. ولو صاروا 100,000؟ النظام ببساطة سينهار. هذا بالضبط ما كان يحدث معنا.

بشكل برمجي، الكود المبدئي كان يشبه هذا (مثال بسيط للتوضيح بلغة Python):

def find_nearest_driver_naive(customer_location, all_drivers):
    """
    الطريقة الساذجة والبطيئة لإيجاد أقرب سائق
    """
    nearest_driver = None
    min_distance = float('inf')  # نبدأ بمسافة لا نهائية

    for driver in all_drivers:
        distance = calculate_distance(customer_location, driver.location)
        if distance < min_distance:
            min_distance = distance
            nearest_driver = driver
    
    return nearest_driver

# الاستخدام
# drivers = get_all_10000_drivers_from_db()
# nearest = find_nearest_driver_naive(customer_location, drivers)
# هذه العملية كانت تستغرق وقتًا طويلاً جدًا!

كان واضحًا أننا بحاجة إلى طريقة أذكى، طريقة لا تتطلب منا “سؤال كل شخص في المدينة” عن مكانه.

المنقذ الذي ظهر فجأة: ما هي الأشجار الرباعية (Quadtrees)؟

الشجرة الرباعية، أو Quadtree، هي هيكل بيانات (Data Structure) عبقري مصمم خصيصًا لتنظيم النقاط في فضاء ثنائي الأبعاد (مثل خريطة). الفكرة بسيطة بشكل مدهش: “قسّم تَسُد”.

تخيل معي خريطة المدينة كلها كمربع كبير. الشجرة الرباعية تقوم بالآتي:

• تقسّم هذا المربع الكبير (الفضاء) إلى أربعة مربعات أصغر متساوية (شمال غربي، شمال شرقي، جنوب غربي، جنوب شرقي).
• لكل مربع من هذه المربعات، يتم التحقق من عدد النقاط (السائقين) الموجودة فيه.
• إذا كان عدد النقاط في مربع ما أكبر من حد معين (مثلاً، 4 سائقين)، يتم تقسيم هذا المربع بدوره إلى أربعة مربعات أصغر.
• تستمر عملية التقسيم هذه بشكل متكرر (Recursively) حتى يصبح كل مربع يحتوي على عدد مقبول من النقاط أو يصل إلى أقصى عمق مسموح به.

النتيجة هي هيكل يشبه الشجرة، حيث كل “عقدة” (Node) في الشجرة تمثل منطقة جغرافية (مربع)، وإذا كانت العقدة تحتوي على أبناء، فهم يمثلون الأرباع الأربعة لتلك المنطقة.

ببساطة، بدلًا من قائمة طويلة من السائقين، أصبح لدينا خريطة مقسمة بشكل هرمي وذكي.

كيف تعمل الأشجار الرباعية على تقسيم الفضاء؟

عند إضافة سائق جديد إلى الشجرة، تبدأ العملية من الجذر (المربع الأكبر الذي يغطي الخريطة كلها). يتم تحديد في أي ربع من الأرباع الأربعة يقع هذا السائق. ثم ننتقل إلى ذلك الربع ونكرر العملية: في أي ربع من أرباعه الفرعية يقع السائق؟ نستمر في النزول في الشجرة حتى نصل إلى “ورقة” (Leaf Node) – وهي منطقة لم يتم تقسيمها بعد. نضيف السائق إلى هذه الورقة. إذا أصبحت هذه الورقة ممتلئة الآن، نقوم بتقسيمها.

هذا التقسيم الديناميكي هو سر قوة الأشجار الرباعية.

من النظرية إلى التطبيق: كيف طبقنا الأشجار الرباعية؟

الحكي النظري جميل، لكن كيف طبقنا هذا بشكل عملي؟ اتبعنا الخطوات التالية:

1. بناء الشجرة في الذاكرة

قررنا أن نحتفظ بالشجرة الرباعية في ذاكرة الخادم (In-memory) لسرعة الوصول. قمنا بإنشاء عملية تعمل في الخلفية (Background Job) تقوم بالآتي كل 10 ثوانٍ:

• تجلب أحدث إحداثيات لجميع السائقين النشطين من قاعدة البيانات.
• تقوم ببناء شجرة رباعية جديدة تمامًا من هذه الإحداثيات.
• بمجرد أن تصبح الشجرة الجديدة جاهزة، يتم استبدال الشجرة القديمة بها بشكل فوري.

هذا يضمن أن البيانات التي نبحث فيها محدّثة دائمًا (بفارق 10 ثوانٍ كحد أقصى، وهو مقبول جدًا).

هيكل البيانات الأساسي للشجرة يمكن أن يبدو هكذا (مثال توضيحي):

class QuadTree:
    def __init__(self, boundary, capacity):
        self.boundary = boundary  # حدود المنطقة (x, y, width, height)
        self.capacity = capacity  # أقصى عدد من النقاط قبل التقسيم
        self.points = []          # النقاط في هذه العقدة
        self.divided = False      # هل تم تقسيم هذه العقدة؟

    def subdivide(self):
        # ... منطق تقسيم المنطقة إلى أربعة أرباع
        # self.northwest = QuadTree(...)
        # self.northeast = QuadTree(...)
        # ... وهكذا
        self.divided = True

    def insert(self, point):
        # إذا كانت النقطة خارج الحدود، تجاهلها
        if not self.boundary.contains(point):
            return False

        # إذا كان هناك مكان، أضف النقطة
        if len(self.points) < self.capacity:
            self.points.append(point)
            return True
        else:
            # إذا لم تكن مقسمة، قم بالتقسيم الآن
            if not self.divided:
                self.subdivide()
            
            # أدخل النقطة في الربع الصحيح
            if self.northwest.insert(point): return True
            if self.northeast.insert(point): return True
            if self.southwest.insert(point): return True
            if self.southeast.insert(point): return True

2. الاستعلام عن أقرب سائق (اللحظة السحرية)

الآن، عندما يأتي طلب جديد من زبون، بدلًا من البحث في 10,000 سائق، نقوم بالآتي:

1. نحدد المربع (العقدة الورقية) الذي يقع فيه الزبون بالنزول في الشجرة.
2. نبحث عن أقرب سائق داخل هذا المربع الصغير. هذا يعطينا مرشحًا أوليًا وأقصر مسافة أولية.
3. وهنا يكمن الذكاء: بدلًا من التوقف، نرسم دائرة حول الزبون نصف قطرها هو “أقصر مسافة وجدناها حتى الآن”.
4. نبدأ بالتحقق من المربعات المجاورة. لكننا لا نتحقق من كل المربعات! نتحقق فقط من المربعات التي تتقاطع مع هذه الدائرة. إذا كان المربع بأكمله أبعد من أقرب سائق وجدناه، نتجاهله تمامًا هو وجميع السائقين بداخله!

هذه العملية، التي تسمى “Pruning” أو “التقليم”، هي ما يجعل البحث سريعًا جدًا. نحن نستبعد مناطق جغرافية كاملة من البحث بلمح البصر لأننا نعرف رياضيًا أنه من المستحيل أن تحتوي على سائق أقرب من الذي وجدناه بالفعل.

النتيجة؟ بدلًا من 10,000 عملية حساب مسافة، قد نحتاج فقط إلى 50 أو 100 عملية في أسوأ الحالات.

النتائج كانت مذهلة: أرقام تتحدث عن نفسها

بعد تطبيق الحل الجديد، كانت النتائج فورية ومبهرة:

• قبل: متوسط زمن الاستعلام تحت الضغط: ~45-60 ثانية.
• بعد: متوسط زمن الاستعلام تحت نفس الضغط: ~50-100 ميلي ثانية!

نعم، قرأتم الرقم صحيحًا. تحولنا من دقيقة كاملة إلى أقل من عُشر الثانية. لم نقم فقط بحل المشكلة، بل قمنا ببناء نظام قادر على التوسع والتعامل مع مئات الآلاف من السائقين في المستقبل دون أي قلق. شعور الراحة الذي غمر الفريق في تلك اللحظة لا يوصف، والله. 😉

نصائح من أبو عمر (من قلب الميدان)

من خلال هذه التجربة، تعلمت بعض الدروس التي أحب أن أشاركها معكم:

1. متى تستخدم الأشجار الرباعية؟ هي مثالية للبيانات المكانية ثنائية الأبعاد (خرائط، تصميم ألعاب ثنائية الأبعاد). إذا كنت تتعامل مع بيانات ثلاثية الأبعاد، قد تكون هياكل مثل الأشجار الثمانية (Octrees) أفضل. للبيانات ذات الأبعاد الأعلى، انظر إلى k-d trees.
2. وازن عمق الشجرة وسعتها: هناك مقايضة بين الذاكرة والسرعة. شجرة عميقة جدًا (سعة قليلة لكل عقدة) قد تستهلك ذاكرة كبيرة. شجرة ضحلة جدًا (سعة كبيرة) قد تجعل البحث أبطأ قليلًا. القاعدة الجيدة هي البدء بسعة تتراوح بين 4 و 8 نقاط لكل عقدة والتجربة. “بدك توازنها، زي ما بتوازن الملح في الطبخة”.
3. تعامل مع البيانات المتحركة بذكاء: السائقون يتحركون باستمرار. إعادة بناء الشجرة مع كل تحديث موقع هو أمر مستحيل. الحل الذي اتبعناه (إعادة البناء كل 10 ثوانٍ) هو حل عملي جدًا. يمكنك أيضًا تحديث مواقع النقاط داخل الشجرة نفسها، ولكنه أكثر تعقيدًا.
4. لا تخترع العجلة من جديد (إلا للتعلم): فهم كيفية عمل الأشجار الرباعية من الصفر أمر ضروري. لكن في بيئة الإنتاج، استخدم مكتبة جاهزة ومختبرة. هناك مكتبات ممتازة في معظم لغات البرمجة (مثل `d3-quadtree` في JavaScript أو مكتبات متوفرة عبر `pip` في Python) توفر عليك الكثير من الوقت والجهد.

الخلاصة: لا تخف من الخوارزميات!

في النهاية، هذه القصة ليست مجرد حكاية عن الأشجار الرباعية، بل هي تذكير بأهمية فهم هياكل البيانات والخوارزميات الأساسية. كثير من المبرمجين الجدد يركزون على تعلم أطر العمل (Frameworks) والمكتبات، وهذا مهم، لكن القوة الحقيقية تكمن في فهم المبادئ الأساسية التي تحل المشاكل من جذورها.

المشكلة التي واجهناها لم يكن ليحلها خادم أقوى أو قاعدة بيانات أسرع، بل كان حلها يكمن في تغيير طريقة تفكيرنا في المشكلة نفسها. الخوارزميات ليست “بعبعًا” أو شيئًا أكاديميًا معقدًا، بل هي سلاحك وأداتك كمبرمج ومطور لحل مشاكل حقيقية وملموسة.

لذا، في المرة القادمة التي تواجهك فيها مشكلة أداء، قبل أن تفكر في زيادة الموارد، خذ خطوة للوراء، اشرب فنجان قهوة، وفكر: هل هناك طريقة أذكى؟ هل هناك خوارزمية أو هيكل بيانات يمكن أن ينقذ الموقف؟ على الأغلب، الجواب هو نعم. 🚀