B-tree और डेटाबेस इंडेक्स

B-tree क्या है?

• B-tree कई सॉफ़्टवेयर सिस्टमों, खासकर डेटाबेस मैनेजमेंट सिस्टम (DBMS), की आधारभूत संरचना की तरह काम करता है

• MySQL, Postgres, MongoDB, Dynamo आदि index के ज़रिए efficient data retrieval करने के लिए B-tree पर निर्भर करते हैं

• आप सीखेंगे कि B-tree और B+tree कैसे काम करते हैं, डेटाबेस इन्हें index में क्यों इस्तेमाल करते हैं, और UUID को primary key के रूप में इस्तेमाल करना क्यों बुरा विचार हो सकता है

• B-tree डेटा के जोड़ों को, जिन्हें key और value कहा जाता है, ऐसी संरचना में स्टोर करता है जिसे कंप्यूटर प्रोग्रामर tree-जैसी structure कहते हैं

• B-tree node (आयत) और child pointer (nodes को जोड़ने वाली रेखाएँ) से मिलकर बना होता है

• सबसे ऊपर वाले node को root node, सबसे निचले स्तर के node को leaf node, और बाकी सभी node को internal node कहा जाता है

• नीचे B-tree की परिभाषा दी गई है:

  • हर node N key/value pairs स्टोर करता है (जहाँ N, 1 से बड़ा और K से कम या बराबर होता है)
  • हर internal node में कम-से-कम N/2 key/value pairs होते हैं (internal node वह है जो leaf या root नहीं है)
  • हर node में N+1 child होते हैं
  • root node में कम-से-कम एक value और दो child होते हैं, जब तक कि वही एकमात्र node न हो
  • सभी leaf एक ही स्तर पर होते हैं

• B-tree की एक और मुख्य विशेषता sorting है। हर node के अंदर elements को क्रम में रखा जाता है

• इसी sorting के कारण key search बहुत efficiently की जा सकती है। Search root node से शुरू होती है:

  1. देखें कि जिस key को खोजना है, क्या वह node में मौजूद है
  2. अगर नहीं है, तो node में वह स्थान ढूँढें जहाँ key insert की जाएगी
  3. इस बिंदु पर child pointer का अनुसरण करते हुए अगले स्तर पर जाएँ और वही प्रक्रिया दोहराएँ

• इस तरह search करते समय, एक key ढूँढने के लिए tree के हर स्तर पर सिर्फ एक node पर जाना पड़ता है

• B-tree को खास तौर पर इस तरह बनाया गया है कि यह बहुत बड़ी मात्रा के डेटा के साथ भी अच्छा काम करे, जबकि डेटा को long-term storage (disk) पर persist भी रहना हो। इसकी वजह है कि हर node निश्चित संख्या के bytes इस्तेमाल करता है

• B-tree में हर node कितनी values स्टोर कर सकता है, यह उस node को दिए गए bytes और हर key/value pair द्वारा उपयोग किए गए bytes पर निर्भर करता है

B+tree (डेटाबेस के लिए optimized)

• B+tree, B-tree के समान है, लेकिन इसमें ये नियम बदले जाते हैं:
  • key/value pairs केवल leaf nodes में स्टोर किए जाते हैं
  • non-leaf nodes केवल key से जुड़े child pointers स्टोर करते हैं
• MySQL indexes में B+tree की implementation के लिए दो अतिरिक्त नियम भी हैं:
  • non-leaf nodes, N+1 की जगह N child pointers स्टोर करते हैं
  • हर node में "next" और "previous" pointers भी होते हैं, ताकि tree का हर स्तर doubly linked list की तरह भी काम कर सके
• B+tree डेटाबेस के लिए अधिक उपयुक्त होने के दो कारण हैं:
  1. internal nodes को values स्टोर नहीं करनी पड़तीं, इसलिए हर internal node में अधिक keys रखी जा सकती हैं। इससे tree की depth कम करने में मदद मिलती है
  2. सभी values एक ही स्तर पर स्टोर होती हैं और निचले स्तर की linked list के माध्यम से क्रमवार traverse की जा सकती हैं

MySQL में B+tree का उपयोग

• MySQL कई storage engines को support करता है, और सबसे अधिक इस्तेमाल होने वाला engine InnoDB है, जो B+tree पर काफी निर्भर करता है
• वास्तव में InnoDB इस पर इतना निर्भर करता है कि वह table की primary key को tree key के रूप में इस्तेमाल करके पूरा table data B+tree में स्टोर करता है
• हर बार जब आप नई InnoDB table बनाते हैं, तो आपको primary key निर्दिष्ट करनी होती है
• MySQL हर नई table के लिए एक B+tree बनाता है, और primary key के रूप में सेट की गई value tree की key बन जाती है। Value उस row के बाकी column values होते हैं और वे केवल leaf nodes में स्टोर होती हैं
• इस B+tree का हर node default रूप से 16k size पर सेट होता है
• जब भी MySQL को किसी data fragment (key, value आदि) तक पहुँचना होता है, वह disk से पूरी संबंधित page (B+tree node) लोड करता है, भले ही बाकी keys या values की ज़रूरत न हो
• InnoDB tables पर secondary indexes बनाना भी आम बात है। हर secondary index के लिए एक अतिरिक्त persistent B+tree बनाया जाता है, जिसमें key वह column होता है जिसे user ने index के लिए चुना है, और value संबंधित row की primary key होती है

Primary key चुनना: insertion

• Table data B+tree में कैसे व्यवस्थित होगा, यह चुनी गई key पर निर्भर करता है, इसलिए PRIMARY KEY का चुनाव table के पूरे data के disk layout को प्रभावित करता है
• Primary key के रूप में आम तौर पर दो चीज़ें चुनी जाती हैं:
  • integer sequence (BIGINT UNSIGNED AUTO_INCREMENT आदि)
  • UUID (जिसके कई versions हैं)
• अगर आप UUIDv4 primary key इस्तेमाल करते हैं, तो insert करते समय परिणाम इस प्रकार होते हैं:
  1. Insert के लिए किन nodes पर जाना होगा, इसका पहले से अनुमान नहीं लगाया जा सकता
  2. Insert के लिए target leaf node का अनुमान नहीं लगाया जा सकता
  3. Leaf की values sorted नहीं होतीं
• बहुत सारे inserts के दौरान tree के कई nodes (pages) पर जाना पड़ता है, इसलिए समस्या 1 और 2 होती है। यह अतिरिक्त reads और writes performance degradation का कारण बनते हैं
• अगर BIGINT UNSIGNED AUTO_INCREMENT को primary key बनाया जाए:
  1. नई value insert करते समय हमेशा सबसे दाहिने path का अनुसरण होता है
  2. Leaf केवल tree के दाहिने हिस्से में ही जोड़ी जाती हैं
  3. Leaf स्तर पर data insertion order के अनुसार sorted रहता है
• बिंदु 1 और 2 के कारण, लगातार होने वाले कई inserts बार-बार उसी page path पर लौटते हैं, जिससे बहुत सारे key/value pairs insert करते समय I/O requests कम हो जाती हैं

Primary key चुनना: क्रमवार डेटा पढ़ना

• डेटाबेस से time order में data retrieve करना बहुत आम है
• अगर UUIDv4 को primary key के रूप में इस्तेमाल किया जाए, तो search result values की sequence कई non-sequential leaf nodes में बिखर जाती है
• अगर आप क्रमवार insert की गई values ढूँढ रहे हैं, तो search result वाली सभी pages एक-दूसरे के पास होती हैं। कई rows retrieve करते समय वे शायद एक ही page में पास-पास भी हों
• ऐसे query patterns में sequential primary key इस्तेमाल करके पढ़ी जाने वाली pages की संख्या घटाई जा सकती है

Primary key चुनना: size

• Primary key का size भी एक महत्वपूर्ण विचार है। Primary key हमेशा:
  1. इतनी बड़ी होनी चाहिए कि values खत्म न हों
  2. इतनी छोटी होनी चाहिए कि अनावश्यक storage space न ले
• Integer sequences के लिए, छोटी tables में MEDIUMINT (1.6 करोड़ unique values) या INT (4 अरब unique values) इस्तेमाल किए जा सकते हैं
• बड़ी tables के लिए BIGINT इस्तेमाल करना सुरक्षित रहता है (18 क्विंटिलियन तक संभावित values)। BIGINT 64-bit (8-byte) होता है
• UUID आम तौर पर 128-bit (16-byte) होता है, जो MySQL के सबसे बड़े integer type से दोगुना है
• क्योंकि B+tree nodes fixed size के होते हैं, BIGINT इस्तेमाल करने पर UUID की तुलना में हर node में अधिक keys रखी जा सकती हैं। इससे tree उथला होता है और lookups तेज़ होते हैं

B+tree, pages और InnoDB

• B+tree का एक बड़ा लाभ यह है कि आप node size को अपनी ज़रूरत के अनुसार सेट कर सकते हैं
• InnoDB में B+tree nodes आम तौर पर 16k पर सेट होते हैं, जो InnoDB page size है
• Query processing के दौरान (और इसलिए B+tree traversal के दौरान), InnoDB disk से individual rows और columns नहीं पढ़ता। जब भी उसे किसी data fragment तक पहुँचना होता है, वह disk से पूरी संबंधित page लोड करता है
• इसे कम करने के लिए InnoDB कुछ तकनीकों का इस्तेमाल करता है, जिनमें सबसे प्रमुख buffer pool है। Buffer pool, disk की pages और MySQL query execution के बीच InnoDB pages के लिए in-memory cache है
• जब MySQL को कोई page पढ़नी होती है, तो वह पहले देखता है कि क्या वह पहले से buffer pool में है। अगर है, तो वह वहीं से पढ़ लेता है और disk I/O operation को छोड़ देता है। अगर नहीं है, तो disk से page लाकर buffer pool में जोड़ता है और फिर query execution जारी रखता है
• Buffer pool query performance को बेहद बेहतर बनाता है। अगर buffer pool न हो, तो query workload संभालने के लिए कहीं अधिक disk I/O operations करने पड़ें

अन्य स्थितियाँ

• यहाँ मुख्य रूप से sequential keys और random/UUID keys की तुलना पर ध्यान दिया गया है, लेकिन ये सिद्धांत इस बात से परे भी उपयोगी हैं कि आप किस प्रकार की primary key या secondary key पर विचार कर रहे हैं
• उदाहरण के लिए, आप user.created_at timestamp को index key के रूप में इस्तेमाल करने पर विचार कर सकते हैं, जिसमें sequential integer जैसी विशेषताएँ होती हैं। जब तक आप legacy data insert नहीं कर रहे, inserts आम तौर पर हमेशा सबसे दाहिने path पर जाएँगे
• इसके विपरीत, user.email_address string जैसी चीज़ random key जैसी विशेषताओं वाली होती है। Users email के alphabetical order में account नहीं बनाते, इसलिए inserts पूरे B+tree में फैलते हैं

निष्कर्ष

• यहाँ B+tree, indexes और primary key के चुनाव के बारे में काफी कुछ कवर किया गया
• ऊपर से देखने पर यह सरल लग सकता है, लेकिन डेटाबेस की performance को अधिकतम करने के लिए कई सूक्ष्म अंतर ध्यान में रखने पड़ते हैं
• आगे और प्रयोग के लिए interactive B+tree website देख सकते हैं

[GN⁺]

Hacker News राय

• wiki को B-Tree की तरह मैनेज करने की रणनीति का उपयोग करके उसे उपयोगी बनाए रखते हैं

  • जब landing page बहुत ज़्यादा हो जाते हैं, तो links और paragraphs को sub-pages में शिफ्ट कर देते हैं
  • मिलते-जुलते और पुराने links को विषय के अनुसार sibling pages में शिफ्ट कर देते हैं
  • अंततः पुराने documents landing page से तीन स्तर नीचे चले जाते हैं
  • documentation आखिरकार search की समस्या बन जाती है
  • शुक्रवार दोपहर को productively बिताने का अच्छा तरीका है

• मैं लंबे समय से ऐसी किसी चीज़ की तलाश में था, यह शानदार post है

  • काश composite indexes पर भी एक section होता

• शानदार visuals के लिए धन्यवाद

  • Aerospike के ऊपर BTree+ indexing support पर काम किया था
  • expired keys को BTree+ से हटाना चुनौतीपूर्ण था
  • हमने तय किया कि पहले sibling leaf node के भीतर ही एक single-level split को merge किया जाए
  • BTree+ के ऊपर sharding जोड़कर speed बढ़ाई और lock contention कम किया
  • cleanup process के दौरान BTree+ असंतुलित हो सकता है
  • अतिरिक्त cleanup work से बचने के लिए index rebuild feature दिया

• Firefox mobile में cookie modal काम नहीं करता

  • इसे यूज़र को browser में configure करने देना चाहिए

• UUID column को primary key के रूप में इस्तेमाल नहीं करना चाहिए

  • 128-bit int को हर relationship aspect में copy करना पड़ता है
  • ज़्यादातर मामलों में यह पूरी तरह random होता है
  • internal table relationships के लिए bigserial(64-bit) PK का इस्तेमाल करना चाहिए, और application-level identifiers तथा natural keys के लिए UUID(128-bit) का
  • database बहुत खुश हो जाएगा

• बेहतरीन educational material है

  • ऐसे interactive demos बहुत मददगार होते हैं

• अगर disk blocks और B-Tree nodes 16k के हैं, और key, value, और child pointers सभी 8-bit के हैं, तो प्रति node 682 key/value और 683 child pointers स्टोर किए जा सकते हैं

  • तीन-स्तरीय tree 30 करोड़ से अधिक key/value pairs स्टोर कर सकता है
  • प्रत्येक element 8 bytes का होना चाहिए

• शानदार article है

  • InnoDB द्वारा data को B-tree में ही स्टोर करने को clustered index कहा जाता है
  • MyISAM non-clustered index था
  • Oracle आदि में इसे चुनने का विकल्प मिलता है

• ग्राफ में v0, v1, ...v10 का क्या मतलब है, यह पूछा गया

  • क्या यह अलग-अलग pages को दर्शाता है, यह जानना चाहते हैं

• बेहद सुंदर interactive visualization है

  • education और popularization, दोनों दृष्टियों से top-tier है