File organization: pages, heap, sorted files और hashing
लक्ष्य और physical model
Logical relation rows का physical क्रम तय नहीं करता। File organization records की जगह तय करता है और access path query को उन तक पहुँचाता है। इस पाठ में memory comparisons और page transfers का अंतर, capacity की गणना तथा workload के लिए layout का चयन सीखेंगे। Keys तथा selection का ज्ञान चाहिए; अगले दो पाठ indexes समझाते हैं।
अभ्यास में fixed-size disk pages और, जब तक अलग न कहा जाए, fixed-size records हैं। Buffer शुरू में खाली है। एक page read एक I/O है, चाहे उसमें कितने records जाँचे जाएँ। CPU comparisons, seek time, prefetch, logging, directory access तथा output writes तभी गिनेंगे जब प्रश्न कहे। यह cost model है, SSD और hard disk की latency समान होने का दावा नहीं। Cached page दोबारा लेने पर disk read नहीं होता। Cost में index और data दोनों pages हैं या नहीं, पहले लिखें।
1. Capacity और record placement
B page bytes, H fixed header bytes, R record bytes और N records हों। Unspanned record page boundary पार नहीं करता। इसलिए bfr=floor((B−H)/R) और packed file के लिए b=ceil(N/bfr)। अंदर की floor को हटाना गलत है। B=4096, H=96, R=150, N=1000 में usable space 4000 bytes, bfr=26 और b=39 है। पहले 38 pages में 988 records और अंतिम में 12 होंगे। प्रत्येक full page के 100 बचे bytes अगले page को नहीं दिए जा सकते।
हर record के लिए अलग 4-byte slot भी चाहिए तो 150n+4n≤4000 से n=25 मिलेगा। Slotted page का slot identifier record के वर्तमान byte-location तक पहुँचाता है। Page के अंदर record खिसकाने पर slot entry बदलकर RID=(page number, slot number) स्थिर रख सकते हैं। दूसरे page में ले जाने के लिए अतिरिक्त indirection या references का update चाहिए। Variable-length records में असली sizes, slots और free space देखें; average size से exact capacity का दावा न करें।
यदि records explicitly spanned हैं तो payload page boundary पार कर सकता है। Fragment overhead न हो और हर page में 4000 payload bytes हों तो 150000 bytes के लिए ceil(150000/4000)=38 pages हैं। लेकिन एक split record पढ़ने में दो pages लग सकते हैं। यह payload सूत्र लगाने से पहले सभी page headers तथा fragment overhead घटाएँ; unspanned placement में इसका उपयोग न करें।
2. Heap: जहाँ जगह मिले वहाँ record
Heap में search-key ordering नहीं है। Free-space directory खाली जगह वाला page खोज सकती है; directory cache में होने पर insertion सस्ता हो सकता है। इससे arbitrary equality search सस्ता नहीं बनता। कोई अलग access path न हो तो missing key के लिए सभी b pages पढ़ेंगे। Existing unique key का page समान संभावना से चुना गया हो तो linear scan की औसत लागत (b+1)/2 है। अंतिम page कम भरा हो तो यह समान-probability धारणा अलग से जाँचें। Nonunique condition के सभी matches चाहिए तो पहला match मिलने पर scan बंद नहीं कर सकते।
उदाहरण: 500-page heap में बहुत inserts तथा कभी-कभी full reports आते हैं। Free space reuse या append उपयुक्त है और पूरी report 500 pages पढ़ती है। Numeric attribute होने से unordered heap पर binary search नहीं कर सकते। Valid RID पहले से उपलब्ध हो तो record खोजने के बजाय सीधे उसका page पढ़ेंगे, सामान्यतः एक uncached read।
3. Sorted file: range के लिए उपयोगी क्रम
Sorted file में records search key के क्रम में होते हैं। Direct page addressing और boundary comparisons उपलब्ध हों तो binary search logarithmic page reads में candidate page खोजता है। लगभग ceil(log2 b) एक estimate है; exact worst-case count algorithm तथा exact match बनाम lower-bound खोज पर निर्भर है। पहला qualifying page मिलने के बाद interval sequentially पढ़ सकते हैं। Search में पहला result page पहले ही पढ़ लिया गया हो, परिणाम k consecutive pages में हो और बाकी k−1 result pages अभी uncached हों, तो केवल k−1 और reads जोड़ें।
मौलिक उदाहरण: प्रश्न स्पष्ट कहता है कि lower-bound search में 9 reads हुए, जिनमें पहला answer page शामिल है। Answer 12 consecutive pages में फैला है। बाकी 11 answer pages अभी uncached हैं। Total 9+11=20 reads होंगे। यही sorted layout का range लाभ है। लेकिन tightly packed sorted sequence में insertion कई records/pages खिसका सकता है। Overflow area तत्काल movement घटाता है; लंबी chains locality खराब कर सकती हैं और बाद में reorganization की जरूरत हो सकती है। Delete के बाद space reuse और physical compaction अलग काम हैं।
4. Hash files: equality और collisions
Hash function search key से bucket चुनता है। अलग keys एक bucket में आ सकती हैं; stored key से equality फिर भी जाँचें। Static hashing में growth से overflow chain बन सकती है। Exact-key lookup target bucket और आवश्यक overflow pages पढ़ता है। “हमेशा एक I/O” गलत है। Missing key के लिए पूरी chain देखनी पड़ सकती है। सामान्य hash numeric क्रम नहीं बचाता; range query को adjacent buckets पढ़कर पूरा नहीं कर सकते।
Trace: h(k)=k mod 4 और bucket page में दो records। 1,5,9,2,6 डालें। Bucket 1 के primary page में 1,5 तथा overflow में 9 है। Bucket 2 में 2,6 हैं। Directory cached और data pages uncached हों तो 9 खोजने के लिए दो reads, absent 13 के लिए भी दो और 6 के लिए एक read चाहिए। कुल file में खाली जगह होने पर भी skew किसी एक bucket को भर सकता है।
Dynamic hashing growth पर buckets बदलता है। Extendible hashing में चुने गए hash prefix या suffix के d bits से directory बनती है: global depth d और 2^d directory entries। हर bucket की local depth d से बड़ी नहीं होती। Split में local depth बढ़ती है। Directory तभी double होती है जब split होने वाले bucket की local depth global depth के बराबर हो। कई directory entries एक ही bucket को point कर सकती हैं। यह supporting depth है; हर hashing प्रश्न में extendible hashing मानना सही नहीं।
5. चुनाव और गलतियों की जाँच
Heap सरल placement और full scan के लिए, sorted layout ordered/range scan के लिए, तथा अच्छे distribution वाला hash equality के लिए उपयोगी है। Buffering, growth, updates और workload देखकर चुनाव करें। Heap पर index बन सकता है; heap का मतलब index निषिद्ध नहीं। एक key का physical क्रम दूसरी key को क्रमबद्ध नहीं बनाता।
गणना से पहले page overhead, spanning rule, record count, cache state, predicate, सभी matches चाहिए या नहीं और read/write counting लिखें। 10000 records अगर 250 pages में हैं तो cold full scan 250 page reads है, 10000 नहीं। सूत्र तभी उपयोगी है जब उसके assumptions प्रश्न से मिलते हों।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. 4096-byte page, 96-byte header और 150-byte unspanned records हैं; slots नहीं। 1000 records के लिए pages?
A. 38 B. 39 C. 40 D. 26
उत्तर: B
A: 38 spanned गणना है, यहाँ लागू नहीं।
B: Capacity 26 और ceil(1000/26)=39 है।
C: 40 न्यूनतम packed allocation नहीं।
D: 26 records/page हैं, pages नहीं।
P02. Cold 120-page heap पर index नहीं। Key absent साबित करने के worst case में data reads?
A. 1 B. 7 C. 60 D. 120
उत्तर: D
A: Key-to-page map नहीं दिया।
B: Binary search हेतु क्रम नहीं है।
C: आधी file का औसत absence साबित नहीं करता।
D: हर page जाँचना पड़ सकता है।
P03. Sorted search में पहले qualifying page सहित 8 reads हैं। Result 5 consecutive pages में है। बाकी चार result pages अभी uncached हैं। Total?
A. 12 B. 13 C. 40 D. 8
उत्तर: A
A: शेष चार pages जोड़ें: 8+4=12।
B: पहला answer page दो बार गिना।
C: हर result page के लिए search दोहराना नहीं है।
D: चार और answer pages पढ़ने हैं।
P04. h(k)=k mod 4, bucket page capacity 2; 1,5,9 के लिए एक primary और एक overflow page है। Cached directory में absent 13 की search reads?
A. 0 B. 1 C. 2 D. 4
उत्तर: C
A: Hash निकालने से absence सिद्ध नहीं होता।
B: केवल primary page पर्याप्त नहीं।
C: Primary और overflow दोनों जाँचना होगा।
D: केवल target bucket chain चाहिए।
P05. Interval scans के लिए कौन-सा organization search-key क्रम रखता है?
A. Heap B. सामान्य hash file C. Sorted file D. हर organization
उत्तर: C
A: Heap क्रम की गारंटी नहीं देता।
B: सामान्य hash numeric क्रम नहीं रखता।
C: Sorted placement में पास की keys साथ रहती हैं।
D: Logical relation सभी layouts को क्रमबद्ध नहीं करता।
P06. Extendible hashing में full bucket local depth 2 और global depth 3 है। सामान्य split में directory का क्या होगा?
A. हमेशा 16 entries करें B. 8 entries रखकर संबंधित pointers बदलें C. 4 entries करें D. Local depth 4 करें
उत्तर: B
A: Local depth छोटी हो तो doubling जरूरी नहीं।
B: आठ entries में pointers बदलें; local depth 3 होगी।
C: Insertion split में shrinking नहीं चाहिए।
D: एक split में local depth 2 से 3 होती है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन