data-structures - شرح - هياكل البيانات الشجرية




شجرة سوداء حمراء مقابل شجرة ب (2)

الشجرة باللون الأحمر / الأسود هي أكثر أو أقل من الشجرة 2-3-4 ، وهي فقط نوع من شجرة B. أداء الحالة الأسوأ متطابق ، بشرط أن تقوم بالبحث الثنائي لقيم عقدة شجرة B.

العيب الواضح لشجرة B هو مساحة مهدرة ، ولكن اعتمادًا على اللغة / مُخصص الذاكرة المستخدم ، قد تجد أن الشجرة 2-3-4 تستخدم مساحة أقل من الشجرة الحمراء السوداء في المتوسط. على سبيل المثال ، في Java 32-bit ، هناك تقريباً حمولة 8 بايت لكل كائن. (كما أنه يعتمد كثيراً على المُخصص ؛ يقوم IIRC phkmalloc بتصنيف توزيعات صغيرة إلى حجم طاقة تبلغ 2).

للإجابة على قضيتك ،

  1. يتم تقسيم وقت استجابة القرص بالتساوي تقريبًا بين وقت البحث وانتظار تدوير القرص.
  2. يجب أن تكون شجرة B قادرة على التفوق على الشجرة الحمراء-السوداء إذا كنت تقوم بذلك بشكل صحيح (على وجه الخصوص ، يجب أن تكون شجرة B أسرع إذا توجها العقد في cacheline).
  3. لا يلزم أن تكون متجاورة في ملف الصفحة ؛ تحتاج فقط إلى أن تكون متجاورة في مساحة العنوان الظاهرية للعملية. بالنسبة لنظام تشغيل عاقل ، فهو مماثل تمامًا للحالة رقم 1 ، ما لم تكن بياناتك صغيرة بما يكفي بحيث تتلاءم مع الذاكرة في الغالب وتكون عبء ذاكرة memcpy كبيرًا.

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

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

  1. البيانات هي أكثر بكثير مما يمكن للذاكرة التعامل (نطاقات عينة في 10-15 تيرابايت) دفعة واحدة. في هذه الحالة ، أود أن تخزين بنية البيانات على القرص.

  2. البيانات هي أقل نسبيا مقارنة بذاكرة النظام وبالتالي يمكن تخزينها وتشغيلها في الذاكرة نفسها للسرعة.

  3. البيانات أكثر من الذاكرة الحرة وتفترض أنها أقل من حجم مجموعة قريبة من البيانات المحتملة في ملف ترحيل الصفحات. لذلك أنا تخزين بنية البيانات في ملف على القرص والقيام بتعيين الذاكرة من الملف.

الاستنتاجات التي توصلت إليها هي:

بالنسبة للحالة 1 ، ينبغي أن أستخدم B-Tree للوصول بشكل أسرع لأنها تحفظ على التأخر الناتج عن دوران القرص

بالنسبة للحالة 2 ، يجب أن أستخدم Red Black Tree للوصول بشكل أسرع لأن البيانات موجودة على الذاكرة ولا. من العناصر اللازمة ليتم مسحها في حالة أسوأ سيكون أقل من واحد يجب أن أقوم به إذا كنت تستخدم B الأشجار

بالنسبة للحالة 3 ، من المشكوك فيه في هذا ، فإن ملف الصفحة على القرص يستخدم نظام التشغيل الأصلي I / O لتشغيل الملفات ، لذا يجب أن تكون B Tree خيارًا أفضل أو شجرة Red Black؟

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

أستخدم لغة C ++ ، مع شجرة سوداء حمراء وشجرة B ، كلاهما صممت من الصفر. أنا أستخدم مكتبة Boost لتعيين الملفات.

تحديث 1 :: كان قراءة من خلال this المنصب في stackoverflow. حصلت على بعض الأفكار الجيدة ، مما جعلني أشعر أن نوع المقارنات التي قمت بها في هذه الحالات قد يكون معيباً. تم نشر رابط في أكثر الأصوات تصويتًا http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html


لفهم الفرق بين هذه ، اقرأ ما دون نقطتين:

1) "Red-Black Tree" هي "Binary Search Tree" ذات "توازن ذاتي" ، مع كل عقدة مميزة بلون (إما أحمر أو أسود) ولها عمليات إضافية محددة عليها للحفاظ على "التوازن"

2) جميع "Red-Black Tree" s هي "Binary Search Tree" s ، ولكن جميع "Binary Search Tree" ليست "Red-Black Tree" s





large-data