โครงสร้างข้อมูลแบบ 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 นี้มักจะแยกเก็บเป็นไฟล์ดัชนี โดยแยกเป็นอิสระออกไปจากไฟล์ข้อมูล