IT A - Z

Home

IT A - Z
Knowledge Developer Database Internet Resource Forum
 

สารบัญตามตัวอักษร

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z # 		 
 

B-tree

ที่มา SearchNetworking.com

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


(ภาพ SearchNetworking.com)

ในต้นไม้ (tree) เรคคอร์ดได้รับารเก็บในตำแหน่งที่เรียกว่าใบ ชื่อนี้มาจากความจริงว่าเรคคอร์ดเหล่านั้นอยู่ที่จุดปลายเสมอ ไม่มีสิ่งใดอยู่ดหนือ จำนวนมากที่สุดของลูกต่อ node เป็นลำดับของต้นไม้ จำนวนของความต้องการเข้าถึงดิสก์คือความลึก ภาพด้านซ้ายแสดง binary tree สำหรับตำแหน่งเฉพาะเรคคอร์ดในชุดของแปดใบ ภาพด้านขวาแสดง B-tree ของสามลำดับสำหรับเรคคอร์ดเฉพาะในชุดของแปดใบ (ใบที่เก้าไม่มีการจองและได้รับการเรียกว่า null) binary tree ด้านซ้ายมีความลึกของสี่ B-tree ด้านขวามีความลึกของสาม B-tree ยอมให้อย่างชัดเจนกับเรคคอร์ดที่ต้องการได้รับค้นหาเร็วๆกว่า สมมติว่าพารามิเตอร์ระบบอื่นทั้งหมดเป็นเอกลักษณ์ การแลกเปลี่ยนคือ กระบวนการตัดสินใจที่แต่ละ node ซับซ้อนมากกว่าใน B-tree  เมื่อเปรียบเทียบกับ binary tree โปรแกรมทันสมัยต้องการประมวลผลการทำงานใน B-tree แต่โปรแกรมนี้ได้รับการเก็บในหน่วยความจำชั่วคราว จึงเรียกใช้ได้เร็ว

B-tree ในทางปฏิบัติ สามารถเป็นพัน ล้าน หรือพันล้านของเรคคอร์ด ไม่ใช่ใบทั้งหมดเก็บเรคคอร์ดอย่างจำเป็น แต่อย่างน้อยครึ่งหนึ่งได้ทำ ความแตกต่างในความลึกระหว่างเส้นร่าง binary-tree และ B-tree ใหญ่กว่าฐานข้อมูลในตัวอย่างที่แสดงออกมา เพราะ B-tree ในโลกจริงเป็นลำดับสูงกว่า (32, 64, 128 หรือมากกว่า) ความลึกของ B-tree สามารถและทำการเปลี่ยนได้ โดยขึ้นกับจำนวนเรคคอร์ดในฐานข้อมูล การเพิ่มจำนวนมากเพียงพอจะเพิ่มความลึก การลบเรคคอร์ดจำนวนมากเพียงพอจะลดความลึก สื่งนี้ทำให้มั่นใจว่าการทำงานของ B-tree เก็บจำนวนเรคคอร์ดเหมาะสม

 

  
 

ศัพท์เกี่ยวข้อง

algorithm, database, hard disk, RAM,

ดูเพิ่มเติม

Semaphore Corporation ตีพิมพ์เอกสารอัลกอริทึม B-tree

update: 1 เมษายน 2548