Një pemë B është një pemë kërkimi e vetë-balancuar ku secili nyje mban shumë çelësa dhe ka shumë fëmijë (fanout të lartë). Kjo e mban pemën të cekët, duke minimizuar numrin e leximeve të diskut — që është pikërisht ajo që kanë nevojë bazat e të dhënave dhe sisteme fajllash.
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
Nje pemë B+, të gjitha vlerat jetojnë në gjethe dhe gjethet janë të lidhura, prandaj skanime të diapazonit kalojnë në një listë të lidhur të gjethe — ideale për pyetje si WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operacioni | Koha | Disk I/O |
|---|---|---|
| kërkimi | O(log n) | O(lartësia) |
| futje / fshirje | O(log n) | O(lartësia) |
| skanim diapazoni | O(log n + k) | gjethe sekuenciale |
Qasja në disk dhe SSD është renditje të magnitudës më e ngadaltë se memoria, prandaj metrika që ka rëndësi është numri i I/O, jo krahasimet.
Fanout i lartë zvogëlon drastikisht I/O-në duke mbajtur pemën vetëm disa nivele të thella.
Kjo është arsyeja pse pothuajse çdo indeks i bazës relacionale të të dhënave (dhe shumë sisteme fajllash) është ndërtuar në pemë B+ në vend të pemëve të kërkimit binar.
Një bibliotekë pyetjesh intervistash IT me përgjigje të detajuara — nga Junior te Senior.
Dhuro