B-tree คืออะไร (ตอนที่ 1)

B-tree ถูกพัฒนาโดย Rudolf Bayer, Edward M. McCreight เป็น Data Structure ประเภท tree อย่างหนึ่ง แต่แตกต่างกับ Data Structure tree อื่นๆที่โดยมากจะนิยมแตก node เป็น 2 node แต่ะ B-tree นั้น จะเป็น M-way Search tree เพื่อทำให้การค้นหาข้อมูลใน tree นั้น มีประสิทธิภาพอย่างมาก

การทำงานของ B-tree เป็น แตกต่างจากต้นไม้ค้นหาแบบทวิภาค (Binary search tree)เพราะ BST นั้นมีโครงสร้างข้อมูลแบบ internal searching schemes ซึ่งข้อมูลที่นำมาใช้นั้นมีขนาดเล็ก และสามารถบรรจุไว้ใน main memory ได้ แต่ B-tree เป็นโครงสร้างข้อมูลที่นำไปใช้ใน external searching ซึ่งเก็บข้อมูลไว้ใน secondary memory

โครงสร้างของ Binary Search Tree อยู่บนสมมติฐานที่ว่าโครงสร้างทั้งหมดสามารถจัดเก็บอยู่ในหน่วยความจำของเครื่องคอมพิวเตอร์ได้ ถ้าจำนวนข้อมูลมีปริมากเกินกว่าที่จะเก็บไว้ในหน่วยความของเครื่องได้ทั้งหมดก็หมายความว่าต้องเก็บมันไว้ในแผ่นจานแม่เหล็ก ซึ่งกรณีเช่นนี้ Big-O model ก็จะไม่มีความหมายอีกต่อไป ทั้งนี้เนื่องจากว่าการเข้าถึงข้อมูลในแผ่นจานแม่เหล็กนั้นใช้ค่าใช้จ่าย (เวลา) ที่แพงมากจนกระทั่ง running time ไม่มีนัยสำคัญใด ๆ อีกต่อไป

นอกจากนี้แล้วยังมี tree ที่ถูกพัฒนาต่อจาก B-tree อีกหลายชนิด เช่น โครงสร้างข้อมูลแบบ B* - Trees หรือ โครงสร้างข้อมูลแบบ B+ -Tree