نماذج البيانات الهرمية: قائمة المجاورة مقابل مجموعات متداخلة

Question

لدي كتالوج منتج. تتكون كل فئة من عدد مختلف (عميق) للفئات الفرعية. عدد المستويات (العميق) غير معروف، لكنني متأكد تماما من أنه لن يتجاوز 5،6 مستوى. التغييرات في البيانات نادرا ما تقرأ بعد ذلك.

والسؤال هو: ما نوع نموذج البيانات الهرمية أكثر ملاءمة لهذا الموقف. يعتمد المشروع على إطار Django وخصائص تكنولوجيا المعلومات الخاصة به (المسؤول i-face، معالجة النماذج ...) ينبغي النظر فيها.

تشكرات!

Answer 1

Nested sets أفضل للأداء، إذا كنت لا تحتاج إلى تحديثات متكررة أو ترتيب هرمي.

إذا كنت بحاجة إلى تحديثات شجرة أو ترتيب هرمي، فمن الأفضل استخدامها parent-child نموذج البيانات.

انها بسهولة شيدت في Oracle و SQL Server 2005+, ، وليس بسهولة (ولكن لا يزال ممكنا) في MySQL.

Answer 2

كنت أستخدم خوارزمية اجتياز شجرة preorder المعدلة، MPTT، لهذا النوع من البيانات الهرمية. هذا يتيح أداء كبيرا على اجتياز الشجرة وإيجاد الأطفال، إذا كنت لا تمانع كثيرا من عقوبة على التغييرات في الهيكل.

لحسن الحظ Django لديه مكتبة رائعة متاحة لهذا، django-mptt.. وبعد لقد استخدمت هذا في عدد من المشاريع مع الكثير من النجاح. هناك ايضا Django-TreeBeard. الذي يوفر العديد من الخوارزميات البديلة، لكنني لم أستخدمها (ولا يبدو أنها شعبية مثل MPTT على أي حال).

Answer 3

وفقا لهذه المواد:

http://explainExtended.com/2009/09/24/Adjacency-list-vs-nested-sets-postgresql/ http://explainExtended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/

"MySQL هو النظام الوحيد للأربعة الكبرى (MySQL، Oracle، SQL Server، postgresql) التي يظهر نموذج مجموعات المتداخل أداء لائق ويمكن اعتباره بيانات هرمية مخزنة."

Answer 4

http://www.sqlsummit.com/adjacencylist.htm.

Answer 5

قائمة المجاورة أسهل بكثير للحفاظ على ومجموعات متداخلة أسرع بكثير للاستعلام.

كانت المشكلة دائما هي أن تحويل قائمة مجاورة إلى مجموعات متداخلة أخذت الطريق لفترة طويلة بفضل طريقة "دفع المكدس" سيئة حقا التي تم تحميلها مع RBAR. لذلك ينتهي الناس في القيام ببعض الصيانة الصعبة حقا في مجموعات متداخلة أو عدم استخدامها.

الآن، يمكنك الحصول على كعكة الخاص بك وتناولها، أيضا! يمكنك القيام بالتحويل على 100،000 Nodesin أقل من 4 ثوان وعلى مليون صف في أقل من دقيقة! كل ذلك في T-SQL، بالمناسبة! يرجى الاطلاع على المقالات التالية.

التسلسلات الهرمية على المنشطات رقم 1: تحويل قائمة مجاورة إلى مجموعات متداخلة

التسلسلات الهرمية على المنشطات رقم 2: بديل لحسابات مجموعات متداخلة