B-tree એ સ્વ-સંતુલિત શોધ વૃક્ષ છે જ્યાં દરેક નોડ ઘણી ચાવીઓ રાખે છે અને ઘણા બાળકો ધરાવે છે (ઉચ્ચ 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.
વિગતવાર જવાબો સાથે IT ઇન્ટરવ્યૂ પ્રશ્નોની લાઇબ્રેરી — જુનિયરથી સિનિયર સુધી.
દાન કરો [ 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
| ક્રિયા | સમય | ડિસ્ક I/O |
|---|---|---|
| શોધ | O(log n) | O(ઊંચાઈ) |
| સામેલ કરો / કાઢી નાખો | O(log n) | O(ઊંચાઈ) |
| શ્રેણી સ્કેન | O(log n + k) | ક્રમિક પાંદડાઓ |
ડિસ્ક અને SSD ઍક્સેસ મેમરી કરતાં વ્યાપક રીતે ધીમો છે, તેથી મહત્ત્વપૂર્ણ મેટ્રિક I/O ગણતરી છે, સરખામણી નથી.
ઉચ્ચ fanout વૃક્ષને માત્ર કેટલાક સ્તર ઊંડો રાખીને I/O ને ઘણું ઘટાડે છે.
યही કારણ છે કે લગભગ દરેક સંબંધી ડેટાબેસ ઇન્ડેક્સ (અને ઘણી ફાઇલસિસ્ટમ) B+ trees પર બનાવવામાં આવે છે બજાય બાઈનરી શોધ વૃક્ષ છે.