ข้อแตกต่างระหว่าง B-tree และ Binary tree ก็คือ B-tree ต้องมีโหนดลูกทั้งหมดในระดับเดียวกันในขณะที่ Binary Tree ไม่มีข้อ จำกัด เช่นนี้ ต้นไม้ไบนารีสามารถมีได้สูงสุด 2 subtrees หรือโหนดใน B-tree สามารถมี M ไม่มีของ subtrees หรือโหนดที่ M เป็นคำสั่งของต้นไม้ B
แผนภูมิเปรียบเทียบ
| พื้นฐานสำหรับการเปรียบเทียบ | B ต้นไม้ | ต้นไม้ไบนารี |
|---|---|---|
| ข้อ จำกัด ที่สำคัญ | โหนดสามารถมีจำนวนสูงสุดของโหนดชายน์ (โดยที่ M คือลำดับของทรี) | โหนดสามารถมี subtrees ได้สูงสุด 2 ตัว |
| มือสอง | มันถูกใช้เมื่อข้อมูลถูกเก็บไว้ในดิสก์ | มันถูกใช้เมื่อบันทึกและข้อมูลจะถูกเก็บไว้ใน RAM |
| ความสูงของต้นไม้ | log M N (โดยที่ m คือลำดับของทรี M-way) | บันทึก 2 N |
| ใบสมัคร | โครงสร้างข้อมูลการทำดัชนีรหัสใน DBMS จำนวนมาก | การเพิ่มประสิทธิภาพรหัสการเข้ารหัส Huffman ฯลฯ |
คำจำกัดความของ B-tree
ต้นไม้ B เป็นต้นไม้ทางสมดุล M และยังเป็นที่รู้จักต้นไม้เรียงลำดับที่สมดุล มันคล้ายกับแผนผังการค้นหาแบบไบนารีที่มีการจัดระเบียบโหนดบนพื้นฐานของการข้ามผ่าน inorder ความซับซ้อนของพื้นที่ต้นไม้ B คือ O (n) ความซับซ้อนของการแทรกและการลบเวลาคือ O (บันทึก n)
มีเงื่อนไขบางอย่างที่ต้องเป็นจริงสำหรับต้นไม้ B:
- ความสูงของต้นไม้จะต้องอยู่ในระดับต่ำที่สุดเท่าที่จะทำได้
- เหนือใบไม้ของต้นไม้ไม่ควรมีต้นไม้ย่อยที่ว่างเปล่า
- ใบของต้นไม้จะต้องมาในระดับเดียวกัน
- โหนดทั้งหมดควรมีจำนวนลูกน้อยที่สุดยกเว้นออกจากโหนด
คุณสมบัติของ B-tree ของ order M
- แต่ละโหนดสามารถมีจำนวนชายน์สูงสุดและจำนวนชายด์ขั้นต่ำ M / 2 หรือจำนวนใด ๆ จาก 2 ถึงสูงสุด
- แต่ละโหนดมีหนึ่งคีย์น้อยกว่าชายด์ที่มีคีย์ M-1 สูงสุด
- การจัดเรียงของคีย์อยู่ในลำดับเฉพาะบางอย่างภายในโหนด คีย์ทั้งหมดในทรีย่อยที่อยู่ทางด้านซ้ายของคีย์นั้นเป็นรุ่นก่อนหน้าของคีย์และปุ่มที่อยู่ทางขวาของคีย์จะเรียกว่าตัวตายตัวแทน
- ในช่วงเวลาของการแทรกโหนดเต็มรูปแบบต้นไม้แยกออกเป็นสองส่วนและคีย์ที่มีค่ามัธยฐานถูกแทรกที่โหนดหลัก
- การผสานจะเกิดขึ้นเมื่อมีการลบโหนด
ความหมายของต้นไม้ไบนารี
ต้นไม้ไบนารีเป็นโครงสร้างต้นไม้ที่สามารถมีตัวชี้อย่างน้อยสองตัวสำหรับโหนดลูก หมายความว่าระดับสูงสุดที่โหนดสามารถมี 2 และอาจเป็นศูนย์หรือโหนดหนึ่งองศาเช่นกัน
มีบางสายพันธุ์ของต้นไม้ไบนารีเช่นต้นไม้ไบนารีอย่างเคร่งครัดต้นไม้ไบนารีสมบูรณ์ต้นไม้ไบนารีขยาย ฯลฯ
- ต้นไม้ไบนารีอย่างเคร่งครัดเป็นต้นไม้ที่แต่ละโหนดที่ไม่ใช่เทอร์มินัลจะต้องมีทรีย่อยและทรีย่อยที่ถูกต้อง
- ต้นไม้ถูกเรียกว่าต้นไม้ไบนารีสมบูรณ์เมื่อมันตรงตามเงื่อนไขของการมี 2 โหนดในแต่ละระดับโดยที่ฉันเป็นระดับ
- เธรดไบนารีเป็นต้นไม้ไบนารีซึ่งประกอบด้วย 0 ไม่มีโหนดหรือจำนวนโหนด 2
เทคนิคการสำรวจเส้นทาง
Tree traversal เป็นหนึ่งในการดำเนินการที่เกิดขึ้นบ่อยครั้งที่สุดในโครงสร้างข้อมูลต้นไม้ซึ่งแต่ละโหนดเข้าชมครั้งเดียวอย่างเป็นระบบ
- Inorder- ในการสำรวจต้นไม้นี้ทรีย่อยด้านซ้ายจะถูกเยี่ยมชมซ้ำ ๆ จากนั้นจะมีการเยี่ยมชมโหนดรูทและทรีย่อยขวาขวาสุดท้าย
- ผู้นำ - ในทรีนี้การแวะผ่านโหนดรูทจะไปที่ทรีย่อยก่อนจากนั้นซ้ายและทรีย่อยที่ด้านขวาสุดท้าย
- Postorder- เทคนิคนี้ไปที่ทรีย่อยทางซ้ายจากนั้นทรีย่อยที่เหมาะสมและที่โหนดรูทสุดท้าย
ความแตกต่างที่สำคัญระหว่าง B-tree กับ Binary tree
- ใน B-tree จำนวนโหนดชายน์สูงสุดที่โหนดที่ไม่ใช่เทอร์มินัลสามารถมีได้คือ M โดยที่ M คือลำดับของ B-tree ในทางกลับกันต้นไม้ไบนารีสามารถมีอย่างน้อยสอง subtrees หรือโหนดเด็ก
- B-tree ใช้เมื่อข้อมูลถูกเก็บไว้ในดิสก์ในขณะที่ต้นไม้ไบนารีจะใช้เมื่อข้อมูลถูกเก็บไว้ในหน่วยความจำเร็วเช่น RAM
- แอปพลิเคชั่นอีกส่วนสำหรับ B-tree คือโครงสร้างข้อมูลการจัดทำดัชนีโค้ดใน DBMS ในทางตรงกันข้ามต้นไม้แบบ Binary นั้นใช้ในการเพิ่มประสิทธิภาพรหัสการเข้ารหัส Huffman เป็นต้น
- ความสูงสูงสุดของทรี B คือล็อก M N (M คือลำดับของทรี) เทียบกับความสูงสูงสุดของต้นไม้ไบนารีคือล็อก 2 N (N คือจำนวนโหนดและฐานคือ 2 เพราะเป็นแบบไบนารี่)
ข้อสรุป
B-tree ถูกใช้บนแผนผังการค้นหาแบบไบนารีและไบนารีเหตุผลหลักที่อยู่เบื้องหลังคือลำดับชั้นหน่วยความจำที่ CPU เชื่อมต่อกับแคชด้วยช่องสัญญาณแบนด์วิดธ์สูงในขณะที่ CPU เชื่อมต่อกับดิสก์ผ่านช่องสัญญาณแบนด์วิดธ์ต่ำ ต้นไม้ไบนารีถูกใช้เมื่อจัดเก็บเรคคอร์ดใน RAM (เล็กและเร็ว) และใช้ B-tree เมื่อมีการจัดเก็บเรคคอร์ดในดิสก์ (ใหญ่และช้า) ดังนั้นการใช้ B-tree แทน Binary tree ช่วยลดเวลาในการเข้าถึงได้อย่างมากเนื่องจากปัจจัยการแตกกิ่งสูงและลดความสูงของต้นไม้
