تزايد المجموعات المتداخلة في شروط الشبكة

مرحبًا ، اسمي أنطون وأنا مطور. الابن الذي أنجبته ، اشترى المنزل المبني ، وبقي أن تنمو شجرة. نظرًا لأنني لست مهندسًا زراعيًا كثيرًا ، فقد اضطررت إلى ترميز شجرة. يتكون مشروعنا من عدة خدمات مصغرة على .Net Core ، يتم تخزين الكيانات التي تشكل علاقات هرمية في قاعدة بيانات PostgreSQL. سأخبرك ما هي البنية الأفضل أن تختارها لتخزين مثل هذه البيانات ، ولماذا بالضبط المجموعات المتداخلة ، وما هي الأشياء التي يمكنك التقدم إليها ، وكيفية التعايش معها لاحقًا.

ما هي المجموعات المتداخلة

يعلم الجميع كيف تنمو الشجرة في الحديقة ، وفي حالة المجموعات المتداخلة ، تنمو الشجرة على النحو التالي: لكل عقدة ، يتم تخزين حقلين يسار ويمين ، وهما عددان صحيحان. المنطق هنا هو أن Left أقل من Right ، وإذا كانت العقدة بها أطفال ، فيجب أن تكون جميع القيم اليسرى واليمنى للعقد الفرعية بين القيم المقابلة للأصل.

كيف ينمون معنا

لقد خصصنا خدمة مصغرة منفصلة لتخزين التسلسلات الهرمية. غالبًا ما يتعين على الواجهة رسم شجرة كاملة بالإضافة إلى الأشجار الفرعية للعناصر في عرض التفاصيل ، بينما يعد إدراج العناصر ونقلها نادرًا نسبيًا. لمثل هذه الحالة ، تعتبر المجموعات المتداخلة مثالية. مخزنة في جدول مثل هذا:





المعرف هو معرف الكيان المقابل ، وباستخدامه يمكنك الحصول على معلومات كاملة من الخدمة المصغرة المناسبة. TreeId هو معرف عنصر الجذر. معظم الأشجار الموجودة في المشروع صغيرة ولكن يوجد الكثير منها. يتم استخدام EntityFramework للقراءة من قاعدة البيانات ، ويقابل الفصل واحدًا إلى واحد في بنية الجدول.

كيف تقرأ

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

dataContext.Nodes.Where(_ => 
                        _.Left > node.Left && 
                        _.Right < node.Right && 
                        _.TreeId == node.TreeId); 

عملية أخرى يتم إجراؤها بشكل متكرر هي العثور على جميع العقد الأصلية للكائن. هنا ، أيضًا ، ليس صعبًا - نطلب عقدًا شجرية يكون يسارها أقل من يسار العنصر الأصلي ، بينما يكون اليمين أكبر على التوالي. على سبيل المثال ، بهذه الطريقة:

dataContext.Nodes.Where(_ => 
                        _.Left < node.Left && 
                        _.Right > node.Right && 
                        _.TreeId == node.TreeId);

كيف تنمو فروع جديدة

دعنا ننتقل إلى الجزء الصعب - الزرع ، أي إضافة عقد أو الانتقال من شجرة فرعية إلى أخرى. دعونا نتعرف على كيفية إجراء التحويل لأن تتضمن هذه العملية بشكل أساسي كل ما تحتاجه لإضافة عنصر تابع.



أول شيء يجب القيام به لإدراج ناجح هو السماح بعملية إدخال أو تحديث واحدة فقط. للقيام بذلك ، سوف نستخدم الحظر. ليس من المنطقي قفل الجدول بأكمله ، نظرًا لأن العقد يمكنها التنقل داخل شجرة واحدة فقط ، لذلك يكفي قفل هذه الشجرة فقط. للقيام بذلك ، قم بتنفيذ استعلام SQL التالي:

select * from "Nodes" where "TreeId" = <TreeId> for update; 

سيسمح لنا ذلك بقراءة عناصر الشجرة على الفور ، ولكن إذا احتجنا إلى إضافة أو تغيير عقدة في الشجرة حيث بدأت هذه العملية بالفعل ، فسيتعين علينا الانتظار حتى تكتمل العملية السابقة.



الخطوة التالية هي تجهيز المكان للزراعة - خلق فجوة بين اليسار واليمين. لنحسب مقدار المساحة المطلوبة - هذا هو الفرق بين يمين ويسار عنصر جذر الشجرة الفرعية التي يتم نقلها. دعونا نضيف هذا الاختلاف لجميع أبناء العقدة التي ستصبح الوالد الجديد. يمكننا التقاط Exception هنا ، وإليك السبب. لتسريع البحث والقراءة في الجدول ، تم إعداد فهارس B-Tree ، في الحقلين الأيسر والأيمن ، وإذا قمت بتغيير قيم هذه الحقول في نفس الوقت ، فقد ينتج عن EntityFramework خطأ تبعية دائري ، حيث يمكن إعادة حساب مؤشرين في وقت واحد على سطر واحد. سيكون الخطأ من النوع InvalidOperationException بالرسالة التالية:

تعذر حفظ التغييرات بسبب اكتشاف تبعية دائرية في البيانات المراد حفظها: "العقدة [المعدلة] <- الفهرس {'Right'، 'TreeId'} العقدة [المعدلة] <- الفهرس {'Left'، 'TreeId'} عقدة [معدلة] '.

للالتفاف ، سنقوم فقط بعمل حلقتين منفصلتين - في واحدة سنقوم بتغيير اليسار ، والأخرى على اليمين ، وبالطبع سنحفظ التغييرات بعد كل منهما.

            var nodesToMove = await dataContext.Nodes 
                .Where(n => 
                    n.Right >= parentNodeRight && 
                    n.TreeId == parentNode.TreeId) 
                .OrderByDescending(n => n.Right) 
                .ToListAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Left += distance; 
            } 
 
            await dataContext.SaveChangesAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Right += distance; 
            } 
 
            await dataContext.SaveChangesAsync(); 

علاوة على ذلك ، فإن عملية الزرع نفسها - ستكون مسافة النقل مساوية للفرق بين يسار الوالد الجديد واليسار من جذر الشجرة الفرعية. أضف هذه القيمة إلى اليسار واليمين لجميع العقد في الشجرة الفرعية التي نتحركها.

            var nodes = await dataContext.Nodes 
                .Where(n => 
                    n.Left >= node.Left && 
                    n.Right <= node.Right && 
                    n.TreeId == node.TreeId) 
                .ToListAsync(); 
 
            foreach (var n in nodes) 
            { 
                n.Left += distance; 
                n.Right += distance; 

وآخر شيء يجب فعله هو سد الفجوة حيث تم نقل الشجرة الفرعية. دعنا نطلب جميع العقد الموجودة على يمين هذه الشجرة الفرعية - ستكون هذه العناصر التي يكون يمينها أكبر من أو يساوي يسار جذر الشجرة الفرعية ، وننقلها إلى المساحة الخالية. للقيام بذلك ، اطرح من اليسار واليمين لكل هذه العقد الفرق بين يمين ويسار الجذر. هنا أيضًا ، عليك القيام بحلقتين منفصلتين:

            var nodesToMove = await dataContext.Nodes 
              .Where(n => n.Right >= gap.Left && n.TreeId == gap.TreeId) 
              .ToListAsync(); 
            nodesToMove = nodesToMove 
                .Where(n => n.Right >= gap.Right) 
                .OrderBy(n => n.Right) 
                .ToList(); 
 
            foreach (var n in nodesToMove) 
            { 
                if (n.Left >= gap.Right) 
                { 
                    n.Left -= distance; 
                } 
            } 
 
            await dataContext.SaveChangesAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Right -= distance; 
            } 
 
            await dataContext.SaveChangesAsync();

خاتمة

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