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+ மரங்களின் அடிப்படையில் கட்டப்பட்டுள்ளன.