คำนิยาม
ในวิทยาศาสตร์คอมพิวเตอร์ต้นไม้ B เป็นต้นไม้ที่มีการปรับสมดุลตนเองที่เก็บข้อมูลตามลำดับ โครงสร้างข้อมูลนี้ช่วยให้การค้นหาข้อมูลการเข้าถึงแบบต่อเนื่องการแทรกข้อมูลและการลบการดำเนินการที่จะเสร็จสิ้นในเวลาลอการิทึม
ทำไมต้องแนะนำ B-Tree?
ก่อนอื่นรวมถึงต้นไม้สีแดงและสีดำที่เราแนะนำก่อนหน้านี้คือ แผนผังการค้นหาภายใน ที่เก็บอินพุตลงใน หน่วยความจำ
B-Tree เป็นส่วนขยายของอัลกอริทึม Tree Tree ก่อนหน้า รองรับ การค้นหาภายนอก สำหรับตารางสัญลักษณ์ที่บันทึกไว้ใน ดิสก์หรือเครือข่าย ไฟล์เหล่านี้อาจมีขนาดใหญ่กว่าอินพุตที่เราพิจารณามาก่อน (เก็บไว้ในหน่วยความจำยาก)
เนื่องจากเนื้อหาถูกเก็บไว้ในดิสก์ดิสก์ I/O อ่านและเขียนบ่อยเกินไปเนื่องจากความลึกขนาดใหญ่ของต้นไม้ (อัตราการอ่านและการเขียนดิสก์มี จำกัด ) ซึ่งนำไปสู่ประสิทธิภาพการสืบค้นที่ไม่มีประสิทธิภาพ
จากนั้นมันเป็นสิ่งสำคัญอย่างยิ่งที่จะลดความลึกของต้นไม้ ดังนั้นเราจึงแนะนำ B-Tree, แผนผังหลายทาง
คุณสมบัติ
แต่ละโหนดในต้นไม้มีเด็กส่วนใหญ่ (M> = 2);
ยกเว้นโหนดรูทและโหนดใบแต่ละโหนดมีอย่างน้อย [เพดาน (m/2)] เด็ก (โดยที่เพดาน (x) เป็นฟังก์ชั่นที่ใช้ขีด จำกัด บน);
หากโหนดรูทไม่ใช่โหนดใบไม้จะมีเด็กอย่างน้อย 2 คน (กรณีพิเศษ: ไม่มีโหนดรูทสำหรับเด็กนั่นคือโหนดรูทเป็นโหนดใบและต้นไม้ทั้งหมดมีโหนดรากเดียว);
โหนดใบทั้งหมดจะปรากฏในเลเยอร์เดียวกัน (ชั้นล่าง) และโหนดใบเป็นโหนดภายนอกซึ่งบันทึกเนื้อหาคือคีย์และค่า
โหนดอื่น ๆ คือโหนดภายในซึ่งบันทึกดัชนีคือคีย์และถัดไป
คำสำคัญของโหนดภายใน: 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-Tree มีเพียงหนึ่งโหนดรูทและโหนดรูทจะมีคีย์ Sentinel เท่านั้นเมื่อเริ่มต้น
แต่ละคีย์ในโหนดภายในจะเชื่อมโยงกับโหนด คีย์ทั้งหมดมีค่ามากกว่าหรือเท่ากับคีย์ที่เกี่ยวข้องกับโหนดนี้ แต่เล็กกว่าคีย์อื่น ๆ ทั้งหมด
การประชุมเหล่านี้สามารถทำให้รหัสง่ายขึ้นอย่างมาก
รหัส
คลิกเพื่อดาวน์โหลด
การใช้งานรหัสนี้แนะนำคีย์ Sentinel และเอาต์พุตรหัสจะกำจัดมัน
B-Tree ที่มีคีย์ Sentinel ในรหัส (บันทึกภาพในเครื่องเพื่อดูและคำจะชัดเจนขึ้น):
เอาต์พุต B-Tree ด้วยรหัส (บันทึกภาพในเครื่องเพื่อดูและคำจะชัดเจนขึ้น):
คลาสสาธารณะ btree <คีย์ขยาย <key>, ค่า> {// เด็กสูงสุดต่อ b-tree node = m-1 // (ต้องมีแม้กระทั่งและมากกว่า 2) int สุดท้ายคงที่ int m = 4; รูทโหนดส่วนตัว // รูทของความสูง int ส่วนตัว B-Tree; // ความสูงของ b-tree ส่วนตัว int n; // จำนวนคู่คีย์-ค่าใน b-tree // helper b-tree โหนดข้อมูลชนิดข้อมูลส่วนตัวระดับสุดท้ายโหนดระดับสุดท้าย {ส่วนตัว int m; // จำนวนเด็กเข้าส่วนตัว [] เด็ก = รายการใหม่ [M]; // อาร์เรย์ของเด็ก // สร้างโหนดกับ K เด็ก K Node ส่วนตัว (int k) {m = k; }} // โหนดภายใน: ใช้คีย์และโหนดภายนอก // ถัดไปเท่านั้น: ใช้เฉพาะรายการคีย์และค่าส่วนตัวคลาสคงที่ส่วนตัว {คีย์เปรียบเทียบส่วนตัว; วัตถุส่วนตัววาล; โหนดส่วนตัวถัดไป; // ฟิลด์ผู้ช่วยซ้ำไปซ้ำรายการอาร์เรย์รายการสาธารณะ (คีย์ที่เปรียบเทียบได้, Val Object, โหนดถัดไป) {this.key = key; this.val = val; this.next = ถัดไป; }} /*** เริ่มต้น B-Tree ที่ว่างเปล่า */ สาธารณะ btree () {root = new node (0); } /*** ส่งคืนจริงถ้าตารางสัญลักษณ์นี้ว่างเปล่า * @return {@code True} หากตารางสัญลักษณ์นี้ว่างเปล่า {@code false} มิฉะนั้น */ บูลีนสาธารณะ isempty () {ขนาดคืน () == 0; } /*** ส่งคืนจำนวนคู่คีย์-ค่าในตารางสัญลักษณ์นี้ * @return จำนวนคู่คีย์-ค่าในตารางสัญลักษณ์นี้ */ ขนาด int สาธารณะ () {return n; } /*** ส่งคืนความสูงของ B-Tree นี้ (สำหรับการดีบัก) * * @กลับมาความสูงของ B-tree */ ความสูง int สาธารณะ () {return height; } /*** ส่งคืนค่าที่เกี่ยวข้องกับคีย์ที่กำหนด * * @param คีย์คีย์ * @return ค่าที่เกี่ยวข้องกับคีย์ที่กำหนดหากคีย์อยู่ในตารางสัญลักษณ์ * และ {@code null} หากคีย์ไม่ได้อยู่ในตารางสัญลักษณ์ * @throws nullpointerexception ถ้า {@code key} {@code null} * โมฆะ"); } return search (root, key, ความสูง); } @suppresswarnings ("ไม่ได้ตรวจสอบ") การค้นหาค่าส่วนตัว (โหนด X, คีย์คีย์, int ht) {รายการ [] เด็ก = x.children; // โหนดภายนอกไปยังโหนดใบต่ำสุด, traverse ถ้า (ht == 0) {สำหรับ (int j = 0; j <xm; j ++) {ถ้า (eq (key, เด็ก [j] .key)) {return (ค่า) เด็ก [j] .val; }}} // โหนดภายในค้นหาที่อยู่ถัดไปอีกครั้ง {สำหรับ (int j = 0; j <xm; j ++) {ถ้า (j+1 == xm || น้อยลง (กุญแจ, เด็ก [j+1] }}} return null; } /** * แทรกคู่คีย์-ค่าลงในตารางสัญลักษณ์การเขียนทับค่าเก่า * ด้วยค่าใหม่หากคีย์อยู่ในตารางสัญลักษณ์แล้ว * หากค่าคือ {@code null} สิ่งนี้จะลบคีย์ออกจากตารางสัญลักษณ์ได้อย่างมีประสิทธิภาพ * * @param คีย์คีย์ * @param val ค่า * @throws nullpointerexception ถ้า {@code key} คือ {@code null} */ โมฆะสาธารณะใส่ (คีย์คีย์, ค่า val) {ถ้า (key == null) {โยน nullpointerexception ใหม่ } โหนด u = แทรก (รูท, คีย์, 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); root = t; ความสูง ++; } การแทรกโหนดส่วนตัว (โหนด H, คีย์คีย์, ค่า val, int ht) {int j; รายการ t = รายการใหม่ (คีย์, val, null); // โหนดภายนอกโหนดภายนอกซึ่งเป็นโหนดใบ ที่ด้านล่างของต้นไม้ค่าเนื้อหาจะถูกเก็บไว้ถ้า (ht == 0) {สำหรับ (j = 0; j <hm; j ++) {ถ้า (น้อยกว่า (คีย์, h.children [j] .key)) {break; }}} // โหนดภายในภายในโหนดเป็นที่อยู่ถัดไป {สำหรับ (j = 0; j <hm; j ++) {ถ้า ((j+1 == hm) || น้อยลง (คีย์, h.children [j+1] .key)) 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 = โหนดใหม่ (m/2); HM = M/2; สำหรับ (int j = 0; j <m/2; j ++) {t.children [j] = h.children [m/2+j]; } return t; } /*** ส่งคืนการแสดงสตริงของ B-Tree นี้ (สำหรับการดีบัก) * * @return การแสดงสตริงของ B-Tree นี้ */ สตริงสาธารณะ toString () {return toString (รูท, ความสูง, "") + "/ n"; } สตริงส่วนตัว toString (โหนด H, int ht, string intent) {stringbuilder s = new StringBuilder (); รายการ [] เด็ก = h.children; if (ht == 0) {สำหรับ (int j = 0; j <hm; j ++) {s.append (เยื้อง + เด็ก [j] .key + "" + เด็ก [j] .val + "/n"); }} else {สำหรับ (int j = 0; j <hm; j ++) {ถ้า (j> 0) {s.append (เยื้อง + "(" + เด็ก [j] .key + ")/n"); } S.Append (ToString (เด็ก [J] .Next, HT-1, Intent + "")); }} return s.toString (); } // ฟังก์ชั่นการเปรียบเทียบ - ทำเทียบเคียงแทนคีย์เพื่อหลีกเลี่ยงการหล่อบูลีนส่วนตัวน้อยลง (เทียบเคียงได้ K1, เปรียบเทียบ K2) {return K1.Compareto (K2) <0; } บูลีนส่วนตัว eq (เทียบเคียง K1, เทียบเคียง K2) {return k1.compareto (k2) == 0; } /*** หน่วยทดสอบประเภทข้อมูล {@code btree} * * @param args อาร์กิวเมนต์บรรทัดคำสั่ง */ โมฆะคงที่สาธารณะหลัก (สตริง [] args) {btree <สตริงสตริง> st = ใหม่ btree <สตริงสตริง> (); 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 มากขึ้น