B-Trees: उम्मीद से कहीं अधिक जानकारी समेटे हुए एक डेटा संरचना

 (benjamincongdon.me)
20 पॉइंट द्वारा GN⁺ 2025-01-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • हाल ही में Alex Petrov की Database Internals पढ़ते समय DBMS storage engine के implementation तरीके, खासकर B-Tree data structure optimization से जुड़ी बातें सामने आईं
  • यूनिवर्सिटी में B-Tree सीखते समय इसे बस “बेहतर BST” की तरह समझा था, इसलिए यह वास्तव में क्यों इस्तेमाल होता है, यह बात स्पष्ट नहीं हुई थी
  • disk I/O को ध्यान में रखते हुए बड़े पैमाने के डेटा को स्टोर करने और तेज़ी से खोजने के लिए B-Tree संरचना उपयुक्त है
  • यह लेख बताता है कि B-Tree की ज़रूरत क्यों पड़ती है, यह कैसे काम करता है, और वास्तविक implementation में किस तरह के optimization संभव हैं
  • एक node में बहुत-सी keys इकट्ठा करके disk access की संख्या कम करना इसकी प्रमुख विशेषताओं में से एक है

डिस्क के कारण उत्पन्न सीमाएँ

  • यह मानकर चला गया है कि पूरा डेटा memory में फिट नहीं होता
  • disk एक बार में page unit के आधार पर read और write करती है
  • memory access की तुलना में disk access बहुत धीमा होता है
  • इसलिए data structure में data को page-केंद्रित तरीके से रखना और कम-से-कम disk access के साथ अधिक-से-अधिक key comparisons करना ज़रूरी होता है
  • अगर BST को ज्यों-का-त्यों disk में स्टोर किया जाए, तो nodes बिखरे रहने के कारण search count जितनी ही disk accesses बढ़ने की समस्या आती है
  • B-Tree एक node में कई keys रखता है, ताकि disk को एक बार पढ़कर कई keys की तुलना की जा सके

Slot page

  • disk पर data रखते समय उसे “page” unit में manage किया जाता है
  • हर page में header, variable-length data रखने वाले cells, और cell location information स्टोर करने वाला offset pointer array होता है
  • slot page संरचना का फायदा यह है कि key size variable होने पर भी rearrangement का बोझ बढ़ाए बिना sorted order बनाए रखा जा सकता है
  • key delete या insert करते समय वास्तविक data को हिलाने की बजाय सिर्फ pointers को rearrange करना कहीं अधिक efficient होता है
  • उदाहरण के लिए, SQLite ऐसे page structure के भीतर free list रखता है और deleted cell space को reuse करता है

B-Tree lookup

  • B-Tree lookup algorithm सरल है:
    1. root node से शुरू करें
    2. वर्तमान node की separator key देखकर उस child node को खोजें जिसमें search key होने की संभावना है
    3. tree को recursively traverse करें
    4. यदि search key वाला leaf node मिल जाए तो काम पूरा, नहीं तो उसे मौजूद नहीं माना जाता
  • internal nodes में actual data की बजाय केवल separator keys हो सकती हैं, और आम तौर पर actual data सिर्फ leaf nodes में स्टोर होता है
  • node के भीतर keys को efficiently खोजने के लिए, हर node की keys sorted state में रखी जाती हैं ताकि binary search का उपयोग किया जा सके

Separator key compression

  • internal node की separator key के लिए पूरी actual key रखना ज़रूरी नहीं, इतना होना पर्याप्त है कि वह ranges को अलग कर सके
  • उदाहरण के लिए 0xAAAAAA और 0xBBBBBB के बीच फ़र्क करने के लिए ज़रूरी नहीं कि पूरा 0xBBBBBB स्टोर किया जाए; एक छोटा prefix भी काफी हो सकता है
  • जिन databases में key length बड़ी होती है, वहाँ ऐसा compression storage space में बड़ी बचत दे सकता है
  • separator key compression के अलावा prefix और suffix को प्रभावी ढंग से छोटा करने की रणनीतियाँ भी होती हैं
  • क्योंकि leaf nodes की संख्या कहीं अधिक होती है, इसलिए कुछ लोगों का मानना है कि prefix compression performance में और भी बड़ा योगदान देता है

Overflow pages

  • जब किसी node में इतनी अधिक keys हो जाएँ कि वे एक page में समा न सकें, तब overflow pages का उपयोग किया जाता है
  • overflow page में पूरी key जस-की-तस ले जाने की बजाय, node में उसका छोटा prefix छोड़ा जाता है और बाकी हिस्सा अलग स्टोर किया जाता है
  • इससे key existence या range query के समय पहले node में मौजूद prefix को देखा जाता है, और केवल ज़रूरत पड़ने पर ही overflow page पढ़ा जाता है
  • यानी अतिरिक्त pages allocate करने के बावजूद कुल search cost कम की जाती है

Sibling pointers

  • कुछ implementations में nodes के बीच बाएँ और दाएँ sibling nodes के pointers स्टोर किए जाते हैं
  • इससे range lookup के दौरान एक leaf node से सीधे sibling node पर जाते हुए लगातार keys को तेज़ी से traverse किया जा सकता है
  • अगर sibling pointers न हों, तो बार-बार parent node तक ऊपर जाकर फिर नीचे उतरना पड़ता है, जिससे I/O cost बढ़ती है
  • sibling nodes के key ranges आपस में overlap नहीं करते, इसलिए right sibling pointer पर जाने का मतलब “अगली key range” पर पहुँचना सुनिश्चित होता है

B-Tree variants

  • B⁺-Tree के अलावा भी कई तरह की variant data structures मौजूद हैं
  • WiredTiger जैसे “Lazy B-Tree” और Lazy-Adaptive Tree write operations को buffer करके performance बढ़ाते हैं
  • FD-Tree SSD की विशेषताओं के अनुसार डिज़ाइन की गई संरचना है, जो block-level writes जैसी physical constraints को ध्यान में रखती है
  • Bw-Tree(Buzzword Tree) उच्च concurrency और in-memory tree access के लिए optimized data structure है

निष्कर्ष

  • अमूर्त “B⁺-Tree” की अवधारणा और वास्तविक implementation “SQLite का DB format” के बीच optimization और implementation details के कई अंतर मौजूद हैं
  • optimization Big-O complexity को नहीं बदलते, लेकिन वास्तविक वातावरण में database performance और usability पर बड़ा असर डालते हैं
  • यहाँ बताए गए बिंदुओं के अलावा भी हर storage system में काफ़ी सूक्ष्म tuning की ज़रूरत पड़ती है
  • “बस थोड़ी-सी अतिरिक्त जानकारी चाहिए” जैसी बातों के पीछे implementation complexity और debugging की कठिनाई छिपी होती है
  • B-Tree संरचना को अधिक वास्तविक रूप में दिखाने वाले उदाहरण के तौर पर, Designing Data Intensive Applications का B-Tree diagram काफ़ी प्रभावशाली है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-01-05
Hacker News राय

  • पेज की संरचना header, cell, और offset pointer से बनी होती है, और इसका फ़ायदा यह है कि यह variable-size data स्टोर कर सकती है

    • सिर्फ pointer array की position को फिर से rearrange करना होता है, इसलिए लागत कम आती है
    • अगर pointer key के sorted order में arranged हों, तो पेज के अंदर key की असली location महत्वपूर्ण नहीं होती

  • यह B-Tree पर एक बेहतरीन लेख है, जिसमें animation भी शामिल हैं

  • कुछ साल पहले Ibrahim Jaluta के शोध के आधार पर concurrent recovery-capable B-link Tree implement किया था

  • SQLite disk page explorer बनाया, जिससे B-Tree को बेहतर समझने में मदद मिली

  • B-link Tree, concurrency, और locking पर चर्चा नहीं है, लेकिन शायद यह ज़रूरत से ज़्यादा जानकारी होती

  • पुरानी टिप्पणियाँ: Hacker News

  • शानदार लेख है, जो details के महत्व को अच्छी तरह समझाता है

    • LSM-Tree और B-Tree, साथ ही LSM-Tree के साथ तुलना पर एक अतिरिक्त लेख देखना चाहूँगा

  • Golang का उपयोग करके B-Tree implementation पर अच्छा resource है

  • मैं इस लेख का बहुत बड़ा प्रशंसक हूँ, और लेखक की तरह मेरी समझ भी कुछ हद तक 'धुंधली' थी

    • जो लोग अपना mental model मज़बूत करना चाहते हैं, उनके लिए यह बेहतरीन resource है