A B-tree ਇੱਕ self-balancing search tree ਹੈ ਜਿਥੇ ਹਰੇਕ node ਵਿੱਚ ਬਹੁਤ ਸਾਰੀਆਂ keys ਹਨ ਅਤੇ ਬਹੁਤ ਸਾਰੇ children ਹਨ (ਉੱਚ fanout)। ਇਹ tree ਨੂੰ ਕਮ ਡੂੰਘਾ ਰੱਖਦਾ ਹੈ, disk reads ਦੀ ਗਿਣਤੀ ਨੂੰ ਘੱਟ ਕਰਦਾ ਹੈ — ਜਿਸ ਦੀ ਡਾਟਾਬੇਸ ਅਤੇ filesystems ਨੂੰ ਬਿਲਕੁਲ ਜ਼ਰੂਰਤ ਹੈ।
A B-tree ਇੱਕ self-balancing search tree ਹੈ ਜਿਥੇ ਹਰੇਕ node ਵਿੱਚ ਬਹੁਤ ਸਾਰੀਆਂ keys ਹਨ ਅਤੇ ਬਹੁਤ ਸਾਰੇ children ਹਨ (ਉੱਚ fanout)। ਇਹ tree ਨੂੰ ਕਮ ਡੂੰਘਾ ਰੱਖਦਾ ਹੈ, disk reads ਦੀ ਗਿਣਤੀ ਨੂੰ ਘੱਟ ਕਰਦਾ ਹੈ — ਜਿਸ ਦੀ ਡਾਟਾਬੇਸ ਅਤੇ filesystems ਨੂੰ ਬਿਲਕੁਲ ਜ਼ਰੂਰਤ ਹੈ।
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 ਵਿੱਚ, ਸਾਰੀਆਂ values leaves ਵਿੱਚ ਰਹਿੰਦੀਆਂ ਹਨ ਅਤੇ leaves linked ਹਨ, ਇਸ ਲਈ range scans leaves ਦੀ linked list ਵਿਚੋਂ ਲੰਘਦੀਆਂ ਹਨ — WHERE age BETWEEN 20 AND 40 ਵਰਗੀਆਂ queries ਲਈ ਆਦਰਸ਼।
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operation | Time | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Disk ਅਤੇ SSD ਤੱਕ ਰਸਾਈ memory ਨਾਲੋਂ ਬਹੁਤ ਸਾਰੇ ਗੁਣਨ ਦੁਆਰਾ ਧੀਮੀ ਹੈ, ਇਸ ਲਈ ਮਾਪ ਜੋ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ ਉਹ I/O count, comparisons ਨਹੀਂ।
ਉੱਚ fanout tree ਨੂੰ ਸਿਰਫ਼ ਕੁਝ levels ਡੂੰਘਾ ਰੱਖ ਕੇ I/O ਨੂੰ ਬਹੁਤ ਘਟਾਉਂਦਾ ਹੈ।
ਇਹੀ ਕਾਰਨ ਹੈ ਕਿ ਲਗਭਗ ਹਰ relational database index (ਅਤੇ ਬਹੁਤ ਸਾਰੇ filesystems) B+ trees ਉੱਤੇ ਬਣੀਆਂ ਹਨ binary search trees ਦੀ ਬਜਾਏ।