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+ చెట్లపై నిర్మితమైనవి.