ต้นไม้แบบบี

ในวิทยาการคอมพิวเตอร์ ต้นไม้แบบบี (อังกฤษ: B-tree) เป็นโครงสร้างข้อมูลแบบต้นไม้ ซึ่งเก็บข้อมูลที่จัดเรียงแล้ว และพร้อมใช้งานสำหรับการค้นหา การเข้าถึงแบบลำดับ การแทรกข้อมูล การลบข้อมูล ซึ่งประสิทธิภาพการทำงานของมันจะใช้เวลาลอการิทึม (logarithmic time) ต้นไม้แบบบีเป็นโครงสร้างต้นไม้ที่มีลักษณะทั่วไปเหมือนกับต้นไม้ทวิภาค คือ แต่ละปมมีปมลูกได้ไม่เกิน 2 ปม ต้นไม้แบบบีเป็นโครงสร้างข้อมูลที่เหมาะสมที่สุดสำหรับระบบที่มีการอ่านและเขียนบล็อกข้อมูลขนาดใหญ่ ดังนั้นมันจึงมักใช้ในงานฐานข้อมูลและระบบแฟ้ม

ต้นไม้แบบบี อันดับ 2 (Bayer & McCreight 1972) หรืออันดับ 5 (Knuth 1998).

ภาพรวม

ปมภายในต้นไม้แบบบี (ปมที่ไม่ใช่ปมใบ) สามารถมีจำนวนแตกต่างกันอยู่ภายในช่วงที่กำหนดไว้ เมื่อมีการแทรกหรือลบข้อมูลจะทำให้จำนวนปมลูกเปลี่ยนแปลงไป ดังนั้นเมื่อต้องการให้จำนวนของปมลูกอยู่ในช่วงที่กำหนดไว้ ปมภายในอาจจะเชื่อมต่อ หรืออยกออกไป เนื่องจากช่วงของปมลูกได้ถูกกำหนดไว้แล้ว ดังนั้นมันจึงไม่จำเป็นต้องจัดสมดุลใหม่บ่อย ๆ เหมือนกับต้นไม้ค้นหาแบบสมดุลตนเองชนิดอื่น ๆ แต่อาจจะยอมให้เสียพื้นที่ว่างบางส่วนภายในต้นไม้ได้ ถ้ามีบางปมที่มีปมลูกไม่ครบ 2 โดยปกติขอบบนและขอบล่างของจำนวนปมลูกจะถูกตรึงไว้เพื่อการทำงานโดยเฉพาะ ตัวอย่างเช่น ต้นไม้แบบ 2-3 บี ปมภายในแต่ละปมสามารถมีปมลูกได้ 2 หรือ 3 ปม

ปมภายในแต่ละปมของต้นไม้แบบบีจะเก็บคีย์ไว้จำนวนหนึ่ง โดยปกติ จำนวนคีย์ถูกเลือกระหว่าง d และ 2d ในทางปฏิบัติคีน์กินที่ส่วนใหญ่ในปม เลข 2 ซึ่งเป็นตัวคูณ เป็นตัวรับประกันว่าปมนั้นสามารถแบ่งแยก หรือรวมได้ ถ้าปมภายในมี 2d คีย์ การเพิ่มคีย์ให้ปมนั้นสามารถทำด้โดยการแบ่งปมที่มี 2d คีย์ ออกเป็นปมที่มีคีย์ d 2 ปม และเพิ่มคีย์ให้กับปมพ่อแม่ ปมที่แบ่งแยกออกไปแต่ละปมมีจำนวนที่ต้องการน้อยที่สุดของคีย์ ในทำนองเดียวกัน ถ้าปมภายในและปมข้างเคียงของมันต่างก็มีคีย์เท่ากับ d คีย์ คีย์อาจถูกลบจากปมภายในโดยการรวมคีย์เข้ากับปมข้างเคียงของมัน การลบคีย์ทำให้ปมภายในมีคีย์เท่ากับ 2d - 1 คีย์ ส่วนการรวมกับปมข้างเคียงจะเพิ่มคีย์ให้กับมัน d คีย์ บวกกับอีก 1 คีย์จากปมพ่อแม่ของปมข้างเคียง ผลที่ได้จะทำให้มันเป็นปมเต็มที่มี 2d คีย์

จำนวนกิ่ง(หรือปมลูก) จากปมนั้นจะมีมากกว่าจำนวนคีย์ในปมอยู่ 1 ในต้นไม้แบบ 2-3 ปมภายในอาจเก็บหนึ่งคีย์ (โดยมีปมลูก 2 ปม) หรือมี 2 คีย์ (โดยมีปมลูก 3 ปม) บางครั้งต้นไม้แบบีถูกอธิบายโดยใช้พารามิเตอร์ (d + 1) - (2d+1) หรือโดยใช้ลำดับกิ่งที่สูงที่สุด (2d + 1)

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

ต้นไม้แบบบีมีข้อได้เปรียบมากกว่าการทำงานด้วยวิธีอื่นๆ เมื่อเวลาที่ใช้สำหรับการเข้าถึงปมมากกว่าเวลาที่เข้าถึงภายในปม เนื่องจากความสูญเสียที่ใช้ไปสำหรับการเข้าถึงปม อาจทำให้ลดลงไปด้วยการดทำงานหลายอย่างภายในปม สิ่งนี้มักเกิดขึ้นเมื่อปมเก็บในหน่วยความจำสำรอง เช่น ตัวขับดิสก์ การทำให้จำนวนของปมลูกของแต่ละปมภายในมีจำนวนมากที่สุด ทำให้ความสูงของต้นไม้ลดลง และจำนวนการเข้าถึงปมที่ทำให้สูญเสียประสิทธิภาพการทำงานลดลง การทำให้ต้นไม้กลับสู่สภาวะสมดุลใหม่จึงเกิดขึ้นไม่บ่อยครั้ง จำนวนปมลูกที่มากที่สุดขึ้นกับสารสนเทศที่เก็บสำหรับปมลูกแต่ละปม และขนาดของบล็อกดิสก์ที่เต็ม หรือขนาดที่คล้ายคลึงกันในหน่วยความจำสำรอง ในขณะที่ต้นไม้แบบบี 2-3 อธิบายได้ง่ายกว่า ต้นไม้แบบบีในทางปฏิบัติที่ใช้หน่วยความจำสำรองต้องการจำนวนปมลูกในการปรับปรุงประสิทธิภาพ

บรรณานุกรม

• Bayer, R.; McCreight, E. (1972), "Organization and Maintenance of Large Ordered Indexes" (PDF), Acta Informatica, 1 (3): 173–189CS1 maint: ref=harv (link)
• Comer, Douglas (มิถุนายน 1979), "The Ubiquitous B-Tree", Computing Surveys, 11 (2): 123–137, doi:10.1145/356770.356776, ISSN 0360-0300CS1 maint: ref=harv (link).

แหล่งข้อมูลอื่น

• B-Tree animation applet โดย slady