تعريف
في علوم الكمبيوتر ، فإن الشجرة B هي شجرة توازن ذاتية تحتفظ بالبيانات بالترتيب. تتيح بنية البيانات هذه البحث في البيانات والوصول المتسلسل وإدخال البيانات وحذف عمليات الحذف في الوقت اللوغاريتمي.
لماذا تقدم B-tree؟
بادئ ذي بدء ، بما في ذلك الشجرة الحمراء والأسود التي قدمناها سابقًا ، هي شجرة بحث داخلية تخزن الإدخال في الذاكرة .
B-Tree هو امتداد لخوارزمية شجرة التوازن السابقة. وهو يدعم عمليات البحث الخارجية عن جداول الرموز المحفوظة على القرص أو الشبكة . قد تكون هذه الملفات أكبر بكثير من الإدخال الذي نظرنا إليه من قبل (من الصعب تخزينه في الذاكرة).
نظرًا لأن المحتوى يتم تخزينه على القرص ، فإن القرص I/O يقرأ ويكتب بشكل متكرر بسبب العمق الكبير للشجرة (يكون معدل قراءة القرص والكتابة محدودًا) ، مما يؤدي إلى كفاءة الاستعلام غير الفعالة.
ثم من المهم بشكل طبيعي تقليل عمق الشجرة. لذلك ، نقدم شجرة البحث ، شجرة البحث متعددة الاتجاهات.
سمات
تحتوي كل عقدة في الشجرة على الأطفال على معظم M (M> = 2) ؛
باستثناء عقدة الجذر وعقدة الأوراق ، تحتوي كل عقدة على الأقل على [سقف (م/2)] الأطفال (حيث السقف (x) هي وظيفة تأخذ الحد الأعلى) ؛
إذا لم تكن عقدة الجذر عقدة أوراق ، فستكون هناك طفلان على الأقل (حالة خاصة: لا توجد عقدة جذر للأطفال ، أي أن عقدة الجذر هي عقدة ورقة ، والشجرة بأكملها تحتوي على عقدة جذر واحدة فقط) ؛
تظهر جميع عقد الأوراق في نفس الطبقة (الطبقة السفلية) ، والعقد الأوراق هي العقد الخارجية ، والتي تنقذ المحتوى ، وهي المفتاح والقيمة .
العقد الأخرى هي العقد الداخلية ، والتي تحفظ الفهرس ، وهي المفتاح والقادم .
الكلمات الرئيسية للعقد الداخلية: K [1] ، K [2] ، ... ، K [M-1] ؛ و K [i] <k [i+1] ؛
مؤشرات بجانب عقدة المحتوى: p [1] ، p [2] ، ... ، p [m] ؛ حيث يشير P [1] إلى الشجرة الفرعية مع الكلمة الرئيسية التي تقل عن K [1] ، يشير P [M] إلى الشجرة الفرعية مع الكلمة الرئيسية أكبر من K [M-1] ، والآخر P [I] يشير إلى شاشة فرعية مع الكلمة الرئيسية (K [I-1] ، K [i]) ؛
على سبيل المثال: (M = 3)
العثور على وإدراج
للراحة ، يتم استخدام مفتاح Sentinel الخاص هنا ، وهو أصغر من جميع المفاتيح الأخرى ويتم تمثيله بواسطة *.
في البداية ، تحتوي الشجرة B فقط على عقدة جذر واحدة ، وعقدة الجذر تحتوي فقط على مفتاح Sentinel عند تهيئتها.
يرتبط كل مفتاح في عقدة داخلية بالعقدة. جميع المفاتيح أكبر من أو تساوي المفتاح المرتبط بهذه العقدة ، ولكنها أصغر من جميع المفاتيح الأخرى.
يمكن لهذه الاتفاقيات تبسيط الكود بشكل كبير.
شفرة
انقر لتنزيل.
يقدم تطبيق الرمز هذا مفتاح Sentinel ، ويقوم إخراج الكود بإلغاءه.
B-Tree مع مفتاح Sentinel في الكود (احفظ الصورة محليًا للعرض ، وستكون الكلمات أكثر وضوحًا):
إخراج B-Tree بواسطة الكود (احفظ الصورة محليًا لعرضها ، وستكون الكلمات أكثر وضوحًا):
الفئة العامة Btree <Key يمتد قابلة للمقارنة <key> ، القيمة> {// Max Kids Per-Tree Node = M-1 // (يجب أن تكون واضحة من 2) Final Static Final int M = 4 ؛ جذر العقدة الخاص // Root of the B-Tree Private Int ؛ // ارتفاع B-tree الخاص int n ؛ . // عدد الأطفال الاشتراك الخاص [] الأطفال = إدخال جديد [M] ؛ // مجموعة من الأطفال // إنشاء عقدة مع K Kids Private Node (int k) {m = k ؛ }} // العقد الداخلية: استخدم فقط المفتاح و next // العقد الخارجية: استخدم فقط المفتاح وقيمة إدخال الفئة الثابتة الخاصة {مفتاح خاص بالمقارنة ؛ كائن خاص فال العقدة الخاصة المقبل ؛ // حقل المساعد للتكرار عبر إدخالات المصفوفة الإدخال العام (مفتاح مماثل ، كائن Val ، Node Next) {this.key = key ؛ this.val = val ؛ this.next = التالي ؛ }} /*** تهيئة شجرة B فارغة. */ public btree () {root = new node (0) ؛ } /*** إرجاع صحيح إذا كان جدول الرمز هذا فارغًا. * return {code true} إذا كان جدول الرمز هذا فارغًا ؛ {code false} خلاف ذلك */ public boolean isempty () {return size () == 0 ؛ } /*** إرجاع عدد أزواج القيمة الرئيسية في جدول الرمز هذا. * regurn عدد أزواج القيمة الرئيسية في جدول الرمز */ public int size () {return n ؛ } /*** إرجاع ارتفاع هذه الشجرة B (لتصحيح الأخطاء). * * @RETURN ارتفاع هذا B-tree */ public int height () {return height ؛ } /*** إرجاع القيمة المرتبطة بالمفتاح المحدد. * * مفتاح param المفتاح * RETURN القيمة المرتبطة بالمفتاح المحدد إذا كان المفتاح في جدول الرمز * و {code null} إذا لم يكن المفتاح في جدول الرمز * throws nullpointerexception إذا كان مفتاح {code) } البحث عن (الجذر ، المفتاح ، الارتفاع) ؛ } suppressWarnings ("Unchected") البحث عن القيمة الخاصة (Node X ، مفتاح المفتاح ، int ht) {intern [] children = x.children ؛ // العقدة الخارجية لأدنى عقدة ورقة ، اجتياز إذا (ht == 0) {for (int j = 0 ؛ j <xm ؛ j ++) {if (eq ، children [j])) {return (value) children [j] .val ؛ }}} // تقوم العقدة الداخلية بالبحث بشكل متكرر العنوان التالي آخر {for (int j = 0 ؛ j <xm ؛ j ++) {if (j+1 == xm || أقل (مفتاح ، الأطفال [j+1] .key)) {return search (chivers [j] .next ، ht-1) ؛ }}} return null ؛ } /** * إدراج زوج القيمة الرئيسية في جدول الرمز ، والكتابة على القيمة القديمة * مع القيمة الجديدة إذا كان المفتاح بالفعل في جدول الرمز. * إذا كانت القيمة {code null} ، فإن هذا يحذف المفتاح بشكل فعال من جدول الرمز. * * مفتاح param المفتاح * param val القيمة * throws nullPointerException إذا كان {code key} هو {code null} */ public void put (مفتاح المفتاح ، القيمة val) {if (key == null) {throw nullpointerxception ("يجب ألا يكون المفتاح فارغًا") ؛ } node u = insert (الجذر ، المفتاح ، val ، الارتفاع) ؛ // العقدة اليمنى التي تم إنشاؤها بعد الانقسام n ++ ؛ if (u == null) {return ؛ } // بحاجة إلى تقسيم عقدة الجذر الجذر الجذر t = عقدة جديدة (2) ؛ T.Children [0] = إدخال جديد (Root.Children [0] .Key ، null ، root) ؛ T.Children [1] = إدخال جديد (U.Children [0] .Key ، null ، u) ؛ الجذر = ر ؛ الارتفاع ++ ؛ } insert node insert (Node H ، مفتاح المفتاح ، القيمة val ، int ht) {int j ؛ الإدخال t = إدخال جديد (مفتاح ، val ، null) ؛ // العقدة الخارجية العقدة الخارجية ، والتي هي أيضا عقدة ورقة. في الجزء السفلي من الشجرة ، يتم تخزين قيمة المحتوى إذا (ht == 0) {for (j = 0 ؛ j <hm ؛ j ++) {if (أقل (مفتاح ، h.children [j] .key)) {break ؛ }}} // العقدة الداخلية داخل العقدة هي العنوان التالي آخر {for (j = 0 ؛ j <hm ؛ j ++) {if ((j+1 == hm) || أقل (مفتاح ، h.children [j+1] .Key)) {node u = insert (h.children [j ++] if (u == null) {return null ؛ } t.key = U.Children [0] .Key ؛ t.next = u ؛ استراحة؛ }}} لـ (int i = hm ؛ i> j ؛ i--) {h.children [i] = h.children [i-1] ؛ } h.children [j] = t ؛ H.M ++ ؛ if (hm <m) {return null ؛ } else {// split node return split (h) ؛ }} // تقسيم العقدة في نصف عقدة خاصة تقسيم (العقدة H) {node t = node node (m/2) ؛ hm = m/2 ؛ لـ (int j = 0 ؛ j <m/2 ؛ j ++) {t.children [j] = h.children [m/2+j] ؛ } إرجاع t ؛ } /*** إرجاع تمثيل سلسلة لهذه الشجرة B (لتصحيح الأخطاء). * * @إعادة تمثيل سلسلة من هذه الشجرة B. */ public string tostring () {return toString (root ، height ، "") + "/ n" ؛ } سلسلة خاصة toString (Node H ، int ht ، string padent) {StringBuilder s = new StringBuilder () ؛ الدخول [] الأطفال = H.Children ؛ if (ht == 0) {for (int j = 0 ؛ j <hm ؛ j ++) {s.append (phend + children [j] .key + "" + children [j] .val + "/n") ؛ }} else {for (int j = 0 ؛ j <hm ؛ j ++) {if (j> 0) {s.append (endent + "(" + children [j] .Key + ")/n") ؛ } }} return S.ToString () ؛ } // وظائف المقارنة - اجعل قابلاً للمقارنة بدلاً من مفتاح تجنب Casts Boolean أقل (K1 قابلة للمقارنة ، K2 قابلة للمقارنة) {return k1.compareto (k2) <0 ؛ } eq boolean private (k1 قابلة للمقارنة ، k2 قابلة للمقارنة) {return k1.compareto (k2) == 0 ؛ } /*** يختبر الوحدة نوع البيانات {code btree}. * * param args وسيطات سطر الأوامر */ public static void main (string [] args) {btree <string ، string> st = new btree <string ، string> () ؛ St.put ("www.cs.princeton.edu" ، "128.112.136.12") ؛ St.put ("www.cs.princeton.edu" ، "128.112.136.11") ؛ St.put ("www.princeton.edu" ، "128.112.128.15") ؛ St.Put ("www.yale.edu" ، "130.132.143.21") ؛ St.put ("www.simpsons.com" ، "209.052.165.60") ؛ St.put ("www.apple.com" ، "17.112.152.32") ؛ St.Put ("www.amazon.com" ، "207.171.182.16") ؛ St.put ("www.ebay.com" ، "66.135.192.87") ؛ St.put ("www.cnn.com" ، "64.236.16.20") ؛ St.Put ("www.google.com" ، "216.239.41.99") ؛ St.Put ("www.nytimes.com" ، "199.239.136.200") ؛ St.Put ("www.microsoft.com" ، "207.126.99.140") ؛ St.put ("www.dell.com" ، "143.166.224.230") ؛ St.put ("www.slashdot.org" ، "66.35.250.151") ؛ St.Put ("www.espn.com" ، "199.181.135.201") ؛ St.put ("www.weather.com" ، "63.111.66.11") ؛ St.put ("www.yahoo.com" ، "216.109.118.65") ؛ System.out.println ("Cs.Princeton.edu:" + St.Get ("www.cs.princeton.edu") ؛ System.out.println ("Hardvardsucks.com:" + St.Get ("www.harvardsucks.com")) ؛ System.out.println ("Simpsons.com:" + St.Get ("www.simpsons.com")) ؛ System.out.println ("Apple.com:" + St.Get ("www.apple.com")) ؛ System.out.println ("eBay.com:" + St.Get ("www.ebay.com")) ؛ System.out.println ("Dell.com:" + St.Get ("www.dell.com")) ؛ System.out.println ("الحجم:" + st.Size ()) ؛ System.out.println ("الارتفاع:" + st.height ()) ؛ System.out.println (ST) ؛ System.out.println () ؛ }} الإخراج:
Cs.Princeton.edu: 128.112.136.12
Hardvardsucks.com: NULL
simpsons.com: 209.052.165.60
Apple.com: 17.112.152.32
eBay.com: 66.135.192.87
dell.com: 143.166.224.230
الحجم: 17
الارتفاع: 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.google.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpsons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.