ความแตกต่างระหว่าง B-tree และ Binary tree

2019

B-tree และ Binary tree เป็นประเภทของโครงสร้างข้อมูลที่ไม่ใช่เชิงเส้น แม้ว่าเงื่อนไขจะดูเหมือนจะคล้ายกัน แต่แตกต่างกันในทุกด้าน ทรีไบนารีจะใช้เมื่อบันทึกหรือข้อมูลถูกเก็บไว้ใน RAM แทนดิสก์เนื่องจากความเร็วในการเข้าถึง RAM สูงกว่าดิสก์มาก ในทางตรงกันข้ามต้นไม้ B จะถูกใช้เมื่อข้อมูลถูกเก็บไว้ในดิสก์จะช่วยลดเวลาในการเข้าถึงโดยการลดความสูงของต้นไม้และเพิ่มกิ่งในโหนด

ข้อแตกต่างระหว่าง 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)	บันทึก `₂` 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 คือลำดับของทรี) เทียบกับความสูงสูงสุดของต้นไม้ไบนารีคือล็อก ₂ N (N คือจำนวนโหนดและฐานคือ 2 เพราะเป็นแบบไบนารี่)

ข้อสรุป

B-tree ถูกใช้บนแผนผังการค้นหาแบบไบนารีและไบนารีเหตุผลหลักที่อยู่เบื้องหลังคือลำดับชั้นหน่วยความจำที่ CPU เชื่อมต่อกับแคชด้วยช่องสัญญาณแบนด์วิดธ์สูงในขณะที่ CPU เชื่อมต่อกับดิสก์ผ่านช่องสัญญาณแบนด์วิดธ์ต่ำ ต้นไม้ไบนารีถูกใช้เมื่อจัดเก็บเรคคอร์ดใน RAM (เล็กและเร็ว) และใช้ B-tree เมื่อมีการจัดเก็บเรคคอร์ดในดิสก์ (ใหญ่และช้า) ดังนั้นการใช้ B-tree แทน Binary tree ช่วยลดเวลาในการเข้าถึงได้อย่างมากเนื่องจากปัจจัยการแตกกิ่งสูงและลดความสูงของต้นไม้