Ordered indexes: dense, sparse, multilevel और costs
लक्ष्य और शब्दावली
Index search-key values तथा records या नीचे के pages तक पहुँचने का रास्ता रखता है। Search key चुनी गई attribute list है; उसका candidate key होना जरूरी नहीं। Index query का logical answer नहीं, access cost बदलता है। पहले lesson 10 का page और cold-cache model समझें। यहाँ static ordered indexes हैं; अगले पाठ में balanced dynamic trees होंगे।
इस पाठ की textbook terminology स्पष्ट है। Primary index ordered file के ordering key पर है, जो इस convention में सामान्यतः unique है। Clustering index nonunique ordering field पर है। Secondary index उस field पर है जो data file का physical order तय नहीं करती। Products के शब्द अलग हो सकते हैं। SQL PRIMARY KEY logical uniqueness constraint है; अकेले इससे physical क्रम का वादा नहीं मिलता। Clustered locality बताता है, dense search values की coverage बताता है; दोनों अलग गुण हैं।
1. Dense और sparse entries
Dense index file के हर search-key value को represent करता है। Unique values हों तो एक entry प्रति record होगी। Duplicates के लिए एक (key,RID) entry प्रति record रख सकते हैं, या एक distinct-value entry से सभी matching RIDs की list/bucket तक जा सकते हैं। Entry count निकालने से पहले design बताना जरूरी है। Sparse index चुने हुए search values रखता है, जैसे हर data page की पहली key; omitted values खोजने के लिए underlying data का क्रम चाहिए।
मौलिक file: P1 में 3,7,11; P2 में 15,19,23; P3 में 28,32,40 हैं। First-key sparse index (3,P1),(15,P2),(28,P3) होगा। 21 खोजते समय 21 से छोटी या बराबर सबसे बड़ी indexed key 15 चुनेंगे। P2 जाँचकर absence मिलेगा। 28 की equality boundary P3 तक जाती है। Global minimum 3 मालूम होने पर 2 तुरंत absent है। 41 के लिए P3 candidate है, लेकिन match नहीं। Anchor के बीच हर integer मौजूद हो, ऐसा नहीं है।
Duplicates कई pages में फैलें तो target के बराबर अंतिम anchor चुनना पहले matches छोड़ सकता है। एक सही design distinct value को उसके पहले containing page तक ले जाता है और पूरी run scan करता है। दूसरा (key,RID) के क्रम में per-record entries रखता है। Duplicate वाले प्रश्न में convention देखें; यहाँ numeric first-key उदाहरण unique values पर हैं।
2. Secondary access में पूर्ण coverage क्यों
अब unordered heap में P1={3,28,15}, P2={7,32,19}, P3={11,40,23} हों। केवल हर page का पहला दिखाया value रखने पर predecessor rule से 19 नहीं खोज सकते। Preceding indexed value जिस page की है, 19 का उसी page में होना जरूरी नहीं। इसलिए conventional secondary ordered index को हर search value की coverage चाहिए, संभवतः RID lists के जरिए। Index entries sort करने से heap records sort नहीं होते।
Secondary index qualifying RIDs जल्दी देता है। Range की index entries पास-पास हो सकती हैं, जबकि actual rows बहुत बिखरे data pages में हों। Clustering में कई matching rows साथ रखे जा सकते हैं। Query को केवल indexed attributes चाहिए और index-only plan की अनुमति हो तो अतिरिक्त data reads बच सकते हैं। Real systems में visibility checks संभव हैं; exam calculation में no-extra-read assumption लिखें।
3. Entry size और multilevel index
K-byte key, P-byte pointer और U-byte usable index page में fixed-entry capacity f=floor(U/(K+P)) है। यह static-entry formula है। Internal B+ node में p child pointers और p−1 separator keys होते हैं; उसका formula अगले पाठ में अलग है।
Worked design: 48000 unique records और हर data page में 40 records, इसलिए 1200 data pages। Sparse first level में 1200 entries होंगी। U=800 और K+P=16 से f=50। First level के ceil(1200/50)=24 pages हैं। इन sorted pages पर second level की 24 entries एक page में आ जाती हैं। Cold lookup में top page, एक first-level page और एक data page, कुल तीन reads हैं। Top cached हो तो दो disk reads। कुल index storage 24+1=25 pages है, 3 नहीं। Storage और lookup path अलग हैं।
इसी file का dense per-record index 48000 entries रखेगा: 960 first-level pages, 20 second-level pages तथा एक top page। कुल 981 index pages और cold lookup में तीन index reads तथा एक data read। हर level पर ceil करें; fractional page को अगले level में न ले जाएँ। Single top page पर construction रुकता है।
4. Range I/O को अलग हिस्सों में बाँटें
Navigation, leaf scan और row fetching अलग गिनें। उदाहरण में initial navigation तीन index pages पढ़ता है, जिनमें पहला qualifying leaf शामिल है। Range चार leaf pages में है, इसलिए index work 3+(4−1)=6 reads। सारे answers छह uncached clustered data pages में हों तो total 12। यदि 80 matching RIDs अलग-अलग 80 uncached heap pages में हों तो total 86। कई RIDs एक page में हों और cache reread बचाए तो distinct fetched pages गिनें, हर RID के लिए एक page नहीं।
Index-only query और no-extra-visibility-read assumption में इसी उदाहरण का cost छह है। Leaf pages और data pages एक वस्तु नहीं। Leaf में पूरे data records ही रखे हों तो उन्हीं records के लिए अलग fetch न जोड़ें। बहुत अधिक rows लौटाने वाली low-selectivity query में scattered index fetches से full scan बेहतर हो सकता है।
5. Updates, composite keys और pitfalls
Dense insertion नया value या RID जोड़ता है। किसी value का अंतिम record हटे तो उस value की entry हट सकती है। Sparse index में anchor बदलने, page split होने या page हटने पर maintenance चाहिए, भले हर record की entry न हो। “Sparse में update cost नहीं” गलत है। अधिक indexes storage और write maintenance बढ़ा सकते हैं।
(department,salary) का lexicographic index पहले department फिर उसी department में salary का क्रम बनाता है। Department equality तथा salary interval एक contiguous range देता है। केवल salary condition सामान्यतः सभी departments में एक contiguous range नहीं देती। Composite ordering को दोनों attributes की independent sorting न मानें।
समाधान क्रम: entry representation लिखें; data pages निकालें; dense/sparse entry count तय करें; page capacity और हर level की rounding करें; cached levels हटाएँ; आवश्यक data reads जोड़ें; duplicate और index-only स्थितियों की जाँच करें। इससे बिना assumptions वाले “logarithm plus one” formula पर निर्भरता नहीं रहती।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Unique ordered data के 900 pages हैं। Sparse first-key index में प्रति data page एक entry और प्रति index page 40 entries हैं। First-level pages?
A. 22 B. 23 C. 40 D. 900
उत्तर: B
A: 22 pages में केवल 880 entries आएँगी।
B: ceil(900/40)=23।
C: 40 capacity है।
D: 900 entries हैं।
P02. Unique ordered file के anchors (4,P1),(17,P2),(31,P3) हैं। 25 के लिए candidate page?
A. P1 B. P2 C. P3 D. No candidate page
उत्तर: B
A: 4 सबसे बड़ा उपयुक्त anchor नहीं।
B: 17, 25 से बड़ी न होने वाली सबसे बड़ी anchor है।
C: 31 target से बड़ा है।
D: Anchor में न होना absence नहीं है।
P03. Dense design में प्रति distinct value एक entry सभी matching RIDs को point करती है। 1000 rows, 70 distinct values में value entries?
A. 70 B. 1000 C. 1070 D. निर्धारित नहीं हो सकता
उत्तर: A
A: प्रति distinct value एक entry दी गई है।
B: यह अलग per-record design का count है।
C: Rows तथा distinct values जोड़ना गलत है।
D: Design से count निश्चित है।
P04. Navigation पहले answer leaf सहित 3 pages पढ़ता है। Range 4 leaves और 7 distinct uncached data pages में है। Total?
A. 10 B. 13 C. 14 D. 28
उत्तर: B
A: शेष तीन leaves छूट गए।
B: 3+(4−1)+7=13।
C: पहला leaf दो बार गिना।
D: Leaves और data pages का गुणा नहीं है।
P05. Heap पर ordered secondary index का कौन-सा कथन सही है?
A. यह heap को physically sort करता है B. यह duplicate keys रोकता है C. Ordered entries बिखरे data pages को point कर सकती हैं D. Maintenance कभी नहीं चाहिए
उत्तर: C
A: Index क्रम तथा heap क्रम अलग हैं।
B: Duplicates को RID entries/lists से रख सकते हैं।
C: Index scan क्रमबद्ध होने से data locality जरूरी नहीं।
D: Insert, delete और key changes पर maintenance हो सकती है।
P06. Lexicographic (department,salary) क्रम में कौन-सी condition स्वाभाविक रूप से एक contiguous interval है?
A. सभी departments में salary=500 B. department=D और 400≤salary≤600 C. सभी departments में salary≠500 D. हर salary predicate ऐसा है
उत्तर: B
A: अलग departments समान salaries को अलग कर सकते हैं।
B: पहला component fixed और दूसरा bounded होने से interval है।
C: Exclusion कई regions बना सकता है।
D: Leading component महत्वपूर्ण है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन