โครงสร้างข้อมูลแบบ B+ -Tree

โครงสร้างข้อมูลแบบ B+ -Tree มีคล้ายคลึงกับแบบ B-Tree ซึ่งแต่ละโหนดจะต้องมีค่าคีย์อย่างน้อย ½ ของค่าคีย์ทั้งหมดที่จะมีได้เต็มที่ ข้อแตกต่างกันคือ Interior Node ของ B+ - Tree จะมีแต่เพียงค่าคีย์ (ไม่มีค่าแอดเดรสของเรคอร์ดในไฟล์ข้อมูล) และค่าพอยน์เตอร์ชี้ไปยังโหนดอื่นๆ ใน Tree ส่วนโหนดที่เป็น Leaf ทุกค่าจะปรากฎอยู่ใน Leaf Nodes นอกจากนี้ Leaf Node ทุกตัวยังจะเชื่อมโยงค่าคีย์ไปตามลำดับซึ่งจะทำให้สามารถเข้าถึงตัวข้อมูลด้วยวิธีการแบบ Sequential ได้รวดเร็วยิ่งขึ้น

ข้อด้อยของวิธีการจัดแบบ B+ - Tree นี้ คือการค้นหาเรคอร์ดจะต้องเริ่มที่ระดับของ Terminal Nodes ก่อนที่จะค้นหาตำแหน่งจริงของคีย์ ตัวอย่างเช่นถ้าต้องการค้นหาค่าคีย์ = 50 ในโครงสร้างของ B+ -Tree เราต้องค้นหาที่ทุกระดับจึงจะค้นพบ แต่ข้อเด่นของ B+ -Tree คือโดยปกติแล้ว B+ -Tree จะมีระดับของการจัดน้อยชั้นกว่าของ B-tree

โครงสร้างแบบ B+ - Tree นี้ เป็นโครงสร้างมาตราฐานในการจัดดัชนี ของไฟล์ข้อมูล โดยที่จะจัดให้แต่ละ Terminal Node เป็นบล็อกของเรคอร์ดของข้อมูลในไฟล์และโหนดที่ไม่ใช่ Terminal Node คือดัชนีของไฟล์ข้อมูล ซึ่งค่า Non-terminal Node นี้มักจะแยกเก็บเป็นไฟล์ดัชนี โดยแยกเป็นอิสระออกไปจากไฟล์ข้อมูล

โครงสร้างข้อมูลแบบ B* - Trees

Bayer และ McCreight ได้พัฒนาโครงสร้างแบบ B-Tree ต่อไปเป็นแบบ Overflow Technique ซึ่งเรียกว่าเป็น B*-Tree เทคนิคใหม่นี้ได้ปรับปรุงวิธีการแทรกข้อมูล โดยการหมุนค่าคีย์ที่ล้นจากโหนดที่เต็มแล้วไปยังโหนดที่เป็นพี่น้องใกล้เคียงกัน (Sibling) คุณสมบัติของ B*-Tree มีดังนี้

1. B*-Tree คือ M-Way Search Tree ซึ่งมีค่าความสูง >= 1 หรือว่างอยู่

2. โหนดที่ Root จะต้องมีโหนดลูกอย่างน้อย 2 Child (ดังนั้นจะมีค่าอย่างน้อย 1 ค่า) และมีค่าโหนดอย่างมากที่สุด

3. โหนดที่ไม่ใช่ Terminal Node ทุกตัว นอกจากโหนดที่เป็น Root จะต้องมีโหนดลูกอย่างน้อย (2m-2)/3 Child (และดังนั้นจะมีค่าข้อมูลย่อย |(2m-1)/3|-1 ค่า

4. ทุก Terminal จะต้องถูกจัดอยู่ในระดับเดียวกัน

5. ทุกโหนดที่ไม่ใช่ Terminal Node ซึ่งค่า k Si มีค่าคีย์เท่ากับ k-1 ค่า



ข้อแตกต่างที่สำคัญระหว่าง B-Tree กับ B*-Tree

ข้อแตกต่างที่สำคัญระหว่าง B-Tree กับ B*-Tree คือ Nodes ภายใน B-Tree (เรียกว่า Interior Node) จะมีอย่างน้อย ½ Tuples ของที่จะจุได้เต็มที่ แต่โหนดภายใน B*-Tree ต้องมีอย่างน้อย 2/3 Tuples ของที่จะจุได้เต็มที่

การลบข้อมูลออกจาก B-tree

การลบค่าข้อมูลออกจาก B-Tree ใช้วิธีการเชื่อมโยง 2 โหนดให้กลายเป็น 1 โหนด แทนที่จะแตกค่าออกเป็น 2 โหนด ทั้งนี้เพื่อให้สามารถคงคุณสมบัติของโครงสร้าง B-Tree เอาไว้ให้ได้ หากเป็นการลบค่าของ Leaf Node จะทำได้ง่ายกว่า คือเป็นการลบค่านั้นๆ ออกจากโครงสร้างเท่านั้น

การใส่ข้อมูลใน b-tree (ตอนที่ 4)

การใส่ข้อมูลนี้ขั้นแรกจะใส่จน root เต็มก่อน เมื่อ root เต็มแล้ว จะแตก tree ออกเป็น child ย่อยๆ ซึ่งการแตกนี้เป็นไปได้หลายกรณี แต่จะแตกโดยใช้หลักการว่า child และ node ที่อยู่ด้าน ซ้ายทั้งหมด จะมีค่าน้อยกว่า ตัวที่อยู่ตรงกลาง และด้านขวา เช่น จากเดิมเรามี 1 และ 4 อยู่ และกำลังจะใส่ 3 ไปดังรูป

เมื่อเราใส่ 3 ไป tree จะแตกออก โดยให้ 3 เป็น root แทน เพราะว่า 1 มีค่าน้อยกว่า 3 และ 4 มีค่ามากกว่า 3 ดังนี้

แต่ถ้าเราใส่ 5 ไป จะกลายเป็นว่า 4 เป็น root แทน เพราะ 4 มีค่ามากกว่า 1 แต่น้อยกว่า 5

การ search ใน b-tree (ตอนที่ 4)

การค้นหาข้อมูลใน B-tree จะเริ่มวิ่งค้นหาจาก root node จน ข้อมูลของเรามีขนาดมากกว่า node ถัดไป หมายความว่า node ที่เรากำหลังอยู่นั้น จะต้องมี child ที่มีค่าอยู่ในช่วงที่เราค้นหา เราจึงลงไปค้นหาด้านล่างต่อไป 

(ตัวอย่างอยู่ด้านใน)

ประสิทธิภาพการทำงานของ B-tree (ตอนที่ 3)

Time complexity in big O notation
	Average	Worst case
Space
Search	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)

คุณสมบัติของ B-Tree (ตอนที่ 2)

1. ใบทุกใบอยู่ในระดับเดียวกัน

2. รากประกอบด้วยลูกอย่างน้อย 2 บัพ และ มีลูกได้ไม่เกิน m บัพ สำหรับบัพภายใน (internal node) อื่น ๆ มีลูกอย่างน้อย m/2 บัพ และ มีลูกมากที่สุด m บัพ

3. ข้อมูลที่เก็บภายในบัพพ่อมีจำนวนน้อยกว่าจำนวนบัพลูกอยู่ 1 ซึ่งข้อมูลเหล่านี้ใช้แบ่งชิ้นข้อมูลที่เก็บในบัพลูก

4. หน่วยข้อมูลเก็บอยู่ที่ leaves

5. โหนดที่ไม่ใช่ leaf เก็บค่าได้ M – 1 ค่าเพื่อเป็นค่าชี้แนะในการค้นหา ค่าที่ i เป็นค่าที่น้อยที่สุดในsubtree ที่ i + 1

6. รากอาจเป็นตัว leaf เอง หรือมีลูกได้ระหว่าง 2 ถึง M

7. โหนดที่ไม่ใช่ leaf ทั้งหมด (ยกเว้นราก) มีลูกได้ตั้งแต่ M/2 ถึง M โหนด

8. leaves ทั้งหมดอยู่ในระดับเดียวกัน และมีค่าข้อมูลตั้งแต่ L/2 ถึง L, สำหรับค่า L ใด ๆ

9. โหนดที่ไม่ใช่ leaf ทุกตัวมีลูกตั้งแต่ 3 ถึง 5 ( ดังนั้นมันมีค่าตั้งแต่ 2 ถึง 3 ค่า); รากอาจมีลูกได้น้อยสุด 2 โหนด

10. เนื่องจาก L = 5 ดังนั้นแต่ละ leaf จึงมีค่าข้อมูลได้ตั้งแต่ 3 ถึง 5 ค่า

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