B-trees અને B+ trees શું છે અને ડેટાબેસ તેનો ઉપયોગ કેમ કરે છે?

Question

IT Interview Practice · Accepted Answer

**B-tree** એ સ્વ-સંતુલિત શોધ વૃક્ષ છે જ્યાં દરેક નોડ **ઘણી ચાવીઓ** રાખે છે અને **ઘણા બાળકો** ધરાવે છે (ઉચ્ચ *fanout*). આ વૃક્ષને **છીછરો** રાખે છે, **ડિસ્ક વાંચન** ની સંખ્યા ઘટાડે છે — જે બરાબર ડેટાબેસ અને ફાઇલસિસ્ટમને જોઈએ છે. ## તે શા માટે મહત્ત્વપૂર્ણ છે ```text 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. ``` ## બંધારણ (B-tree ક્રમ 4) ```text [ 17 | 35 ] / | \ [4|9|12] [20|28] [40|50|60] each node packs many keys -> few levels ``` ## B+ tree સુધાર **B+ tree** માં, *બધી કિંમતો પાંદડાઓમાં જીવે છે* અને પાંદડાઓ **જોડાયેલા** છે, તેથી શ્રેણી સ્કેન પાંદડાઓની જોડાયેલ સૂચી પર ચાલે છે — જે `WHERE age BETWEEN 20 AND 40` જેવી ક્વેરી માટે આદર્શ છે. ```text 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 પર બનાવવામાં આવે છે બજાય બાઈનરી શોધ વૃક્ષ છે.

ક્રિયા	સમય	ડિસ્ક I/O
શોધ	O(log n)	O(ઊંચાઈ)
સામેલ કરો / કાઢી નાખો	O(log n)	O(ઊંચાઈ)
શ્રેણી સ્કેન	O(log n + k)	ક્રમિક પાંદડાઓ

તે શા માટે મહત્ત્વપૂર્ણ છે

બંધારણ (B-tree ક્રમ 4)

B+ tree સુધાર

જટિલતા

તે શા માટે મહત્ત્વપૂર્ણ છે

સંબંધિત પ્રશ્નો