تمثيل الترتيب في قاعدة بيانات علائقية

Question

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

على سبيل المثال، لنفترض أنني أكتب كتابًا، وكل فصل هو كائن.أنا أكتب كتابي، وأرتب الفصول بالترتيب التالي:

المقدمة، إمكانية الوصول، النموذج مقابل.الوظيفة، الأخطاء، الاتساق، الاستنتاج، الفهرس

يذهب إلى المحرر، ويعود بالترتيب المقترح التالي:

المقدمة، النموذج، الوظيفة، إمكانية الوصول، الاتساق، الأخطاء، الاستنتاج، الفهرس

كيف يمكنني تخزين هذا الطلب في قاعدة البيانات بطريقة قوية وفعالة؟

لقد راودتني الأفكار التالية، لكني لست سعيدًا بأي منها:

1. مجموعة مصفوفة.يحتوي كل صف على معرف طلب، وعندما يتم تغيير الطلب (عن طريق الإزالة متبوعة بالإدراج)، يتم تحديث معرفات الطلب.وهذا يجعل عملية الاسترجاع سهلة، لأنها مجرد ORDER BY, ولكن يبدو من السهل كسرها.

   // REMOVAL
UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
// INSERTION
UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
UPDATE ... SET orderID=insertionID WHERE ID=addedID

2. قائمة مرتبطة.يحتوي كل صف على عمود لمعرف الصف التالي في الترتيب.يبدو الاجتياز مكلفًا هنا، على الرغم من أنه قد يكون هناك طريقة ما يمكن استخدامها ORDER BY الذي لا أفكر فيه.

3. مصفوفة متباعدة.قم بتعيين معرف الطلب (كما هو مستخدم في رقم 1) ليكون كبيرًا، بحيث يكون الكائن الأول هو 100، والثاني هو 200، وما إلى ذلك.ثم عندما يحدث الإدراج، ما عليك سوى وضعه في (objectBefore + objectAfter)/2.بالطبع، قد يحتاج هذا إلى إعادة التوازن من حين لآخر، حتى لا يكون لديك أشياء قريبة جدًا من بعضها البعض (حتى مع العوامات، قد تواجه في النهاية أخطاء تقريبية).

لا شيء من هذا يبدو أنيقًا بشكل خاص بالنسبة لي.هل لدى أي شخص طريقة أفضل للقيام بذلك؟

Answer 1

منذ أن واجهت هذا في الغالب مع جانغو، وجدت هذا الحل ليكون الأكثر عملية.يبدو أنه لا توجد "طريقة صحيحة" للقيام بذلك في قاعدة البيانات العلائقية.

Answer 2

سيكون البديل الآخر (إذا كان نظام RDBMS الخاص بك يدعمه) هو استخدام أعمدة من نوع المصفوفة.على الرغم من أن هذا يخالف قواعد التطبيع، إلا أنه قد يكون مفيدًا في مثل هذه المواقف.إحدى قواعد البيانات التي أعرفها والتي تحتوي على صفائف هي PostgreSQL.

Answer 3

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

كملاحظة جانبية، يمكنك إزالة الحاجة إلى القيام دائمًا بإعادة تحديد موضع عمليات الإدراج/الحذف باستخدام الترقيم المتناثر - وهو أمر يشبه إلى حد ما الأساسي في اليوم...يمكنك ترقيم مراكزك 10، 20، 30، إلخ.وإذا كنت بحاجة إلى إدخال شيء ما بين 10 و20، فما عليك سوى إدخاله في الموضع 15.وبالمثل، عند الحذف، يمكنك فقط حذف الصف وترك الفجوة.ما عليك سوى إعادة الترقيم عندما تقوم فعليًا بتغيير الترتيب أو إذا حاولت إجراء إدراج ولا توجد فجوة مناسبة للإدراج فيها.

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

Answer 4

مجرد تفكير في الاعتبار الخيار رقم 1 مقابل رقم 3:ألا يؤدي خيار المصفوفة المتباعدة (#3) إلى تأجيل مشكلة المصفوفة العادية (#1) فقط؟مهما كانت الخوارزمية التي تختارها، فإما أنها معطلة، وستواجه مشكلات مع رقم 3 لاحقًا، أو أنها تعمل، ومن ثم يجب أن يعمل رقم 1 أيضًا.

Answer 5

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

Answer 6

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

أيضًا، أتخيل أن ORDER BY سيتم تحسينه بشكل كبير من قبل بائعي قواعد البيانات، لذا فإن الاستفادة من هذه الوظيفة ستكون مفيدة للأداء بدلاً من تنفيذ القائمة المرتبطة.

Answer 7

استخدم رقم الفاصلة العائمة لتمثيل موضع كل عنصر:

العنصر 1 -> 0.0

البند 2 -> 1.0

البند 3 -> 2.0

البند 4 -> 3.0

يمكنك وضع أي عنصر بين أي عنصرين آخرين عن طريق التنصيف البسيط:

العنصر 1 -> 0.0

البند 4 -> 0.5

البند 2 -> 1.0

البند 3 -> 2.0

(تم نقل البند 4 بين البندين 1 و 2).

يمكن أن تستمر عملية التنصيف إلى أجل غير مسمى تقريبًا نظرًا للطريقة التي يتم بها تشفير أرقام الفاصلة العائمة في نظام الكمبيوتر.

البند 4 -> 0.5

البند 1 -> 0.75

البند 2 -> 1.0

البند 3 -> 2.0

(انقل العنصر 1 إلى الموضع الذي يلي العنصر 4 مباشرة)

Answer 8

سأفعل رقمًا متتاليًا، مع وجود مشغل على الطاولة "يفسح المجال" للأولوية إذا كانت موجودة بالفعل.

Answer 9

كان لي هذه المشكلة أيضا.لقد كنت تحت ضغط كبير من الوقت (ألسنا جميعًا) واختارت الخيار رقم 1، وقمت فقط بتحديث الصفوف التي تغيرت.

إذا قمت بتبديل العنصر 1 بالعنصر 10، فما عليك سوى إجراء تحديثين لتحديث أرقام الطلب الخاصة بالعنصر 1 والعنصر 10.أعلم أن الأمر بسيط من الناحية الخوارزمية، وهو أسوأ حالة O(n)، ولكن أسوأ حالة هي عندما يكون لديك تبديل كامل للقائمة.كم مرة سيحدث ذلك؟هذا لك للرد.

Answer 10

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

لا يزال الحل متقطعًا بعض الشيء ولكن من المرجح أن يعمل بشكل أفضل من الخيار رقم 1، نظرًا لأن الخيار 1 يتطلب تحديث رقم الطلب لجميع الصفوف الأخرى عند طلب التغييرات.

Answer 11

المخطط رقم 1 والمخطط رقم 3 لهما نفس التعقيد في كل عملية باستثناء INSERT يكتب.يحتوي المخطط رقم 1 على كتابة O(n). INSERT والمخطط رقم 3 به O(1) يكتب عليه INSERT.

بالنسبة لكل عملية قاعدة بيانات أخرى، يكون التعقيد هو نفسه.

لا ينبغي حتى النظر في المخطط رقم 2 لأنه DELETE يتطلب O(n) القراءة والكتابة.المخطط رقم 1 والمخطط رقم 3 لهما O(1) DELETE لكل من القراءة والكتابة.

أسلوب جديد

إذا كانت العناصر الخاصة بك تحتوي على عنصر أصل مميز (أييتشاركون في صف مفتاح خارجي)، ثم يمكنك تجربة ما يلي ...

يقدم Django حلاً مستقلاً عن قاعدة البيانات لتخزين قوائم الأعداد الصحيحة داخلها CharField().أحد العوائق هو أن الحد الأقصى لطول السلسلة المخزنة لا يمكن أن يكون أكبر من max_length, ، والذي يعتمد على قاعدة البيانات.

من حيث التعقيد، فإن هذا من شأنه أن يعطي المخطط رقم 1 O(1) للكتابة INSERT, لأنه سيتم تخزين معلومات الطلب كحقل واحد في صف العنصر الأصلي.

عيب آخر هو أن أ JOIN إلى الصف الأصلي مطلوب الآن لتحديث الطلب.

https://docs.djangoproject.com/en/dev/ref/validators/#django.core.validators.validate_comma_separated_integer_list