Ένα B-tree είναι ένα αυτοεξισορροπούμενο δέντρο αναζήτησης όπου κάθε κόμβος κρατά πολλά κλειδιά και έχει πολλά παιδιά (υψηλή fanout). Αυτό διατηρεί το δέντρο ρηχό, ελαχιστοποιώντας τον αριθμό των disk reads — που είναι ακριβώς αυτό που χρειάζονται τα databases και τα συστήματα αρχείων.
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+ tree, όλες οι τιμές ζουν στα φύλλα και τα φύλλα είναι συνδεδεμένα, επομένως οι σάρωση φάσης περπατούν μια συνδεδεμένη λίστα φύλλων — ιδανική για ερωτήματα όπως WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Λειτουργία | Χρόνος | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Η πρόσβαση δίσκου και SSD είναι τάξεις μεγέθους πιο αργή από τη μνήμη, επομένως το μέτρο που σημαίνει είναι ο αριθμός I/O, όχι οι συγκρίσεις.
Η υψηλή fanout μειώνει δραστικά το I/O διατηρώντας το δέντρο μόνο λίγα επίπεδα βαθιά.
Γι' αυτό σχεδόν κάθε ευρετήριο σχεσιακής βάσης δεδομένων (και πολλά συστήματα αρχείων) είναι χτισμένα σε B+ trees παρά σε δυαδικά δέντρα αναζήτησης.