ผลต่างระหว่างรุ่นของ "ต้นไม้แบบบี"

 

==ภาพรวม==

 

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

 

 

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

 

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

 

[[หมวดหมู่:ต้นไม้ (โครงสร้าง)]]