B-ხე არის თვითბალანსირებელი ძებნის ხე, სადაც თითოეული კვანძი ფლობს ბევრ კლავიშს და აქვს ბევრი შვილი (მაღალი fanout). ეს ხეს ზედაპირზე ინახავს, რაც დისკიდან წაკითხვის რაოდენობას მინიმიზирებს — ეს სწორედ ის რაც მონაცემთა ბაზებსა და ფაილსისტემებს სჭირდება.
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
B+ ხეში, ყველა მნიშვნელობა ფოლიოებში მდებარეობს და ფოლიოები დაკავშირებულია, ასე რომ დიაპაზონის სკანირება ფოლიოების დაკავშირებული სიის მეშვეობით მიდის — იდეალური შერჩევებისთვის როგორიცაა WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| ოპერაცია | დრო | დისკის I/O |
|---|---|---|
| ძებნა | O(log n) | O(სიმაღლე) |
| ჩასმა / წაშლა | O(log n) | O(სიმაღლე) |
| დიაპაზონის სკანირება | O(log n + k) | თანმიმდევრული ფოლიოები |
დისკი და SSD-დან წვდომა რამდენჯერმე ნელია მეხსიერების წვდომაზე, ამიტომ მნიშვნელოვანი მეტრიკა არის I/O რაოდენობა, სიდიდეთ არა.
მაღალი fanout მნიშვნელოვნად ამცირებს I/O-ს ხეს რამდენიმე დონის სიღრმეში რჩევისთვის.
ეს არის მიზეზი, რომ თითქმის ყველა რელაციური მონაცემთა ბაზის ინდექსი (და ბევრი ფაილსისტემა) აშენებულია B+ ხეებზე ორობითი ძებნის ხეების ნაცვლად.