फ़ाइल संगठन, B+ वृक्ष, अभिलेन-देन व सहवर्तिता नियंत्रण

दो उप-वस्तुएँ, दोनों यांत्रिक जब आप जान लें कि प्रश्न वस्तुतः कौन-सी राशि माँग रहा है। अनुक्रमण इसलिए विद्यमान है कि डिस्क पठन की लागत एक खंड है, एक बाइट नहीं: दस लाख में एक पंक्ति क्रमवीक्षण से खोजना दस लाख-खंडों की समस्या है, और अनुक्रमणिका उसे मुट्ठी भर में बदल देती है। परीक्षणीय अंकगणित का आकार सदा वही है — किसी खंड में कितनी प्रविष्टियाँ बैठती हैं, अतः अनुक्रमणिका के कितने स्तर हैं, अतः किसी खोज की लागत कितनी खंड-पहुँचें — और B+ वृक्ष के शीर्ष की कोटि ऐसी असमिका का उत्तर है जिसे आप हल करते हैं, वह संख्या नहीं जो आप स्मरण रखते हैं। एक संरचनात्मक तथ्य अधिकांश कार्य करता है: B+ वृक्ष में सब आँकड़ा-सूचक पर्णों में रहते हैं और पर्ण शृंखलित हैं, अतः आंतरिक शीर्ष B वृक्ष के शीर्ष से अधिक कुंजियाँ रख सकता है और परिसर-क्रमवीक्षण नीचे के साथ एक चाल है। तत्पश्चात् अभिलेन-देन, जहाँ सम्पूर्ण विषय भिन्न वेशों में पूछा एक प्रश्न है: यह अंतर्वेशन अभिलेन-देनों को एक के बाद एक चलाने के तुल्य है क्या? उपकरण पूर्वता ग्राफ है — प्रति अभिलेन-देन एक शीर्ष, प्रत्येक संघर्षी युग्म हेतु उनके घटित क्रम में एक किनारा, और अनुसूची संघर्ष-क्रमिकीकरणीय ठीक तब है जब वह ग्राफ अचक्रीय हो। दो संक्रियाएँ केवल तब संघर्ष करती हैं जब वे उसी वस्तु को स्पर्श करें और कम से कम एक लेखन हो, और इसीलिए दो पाठक परस्पर कभी प्रतिबंध नहीं लगाते। सहवर्तिता नियंत्रण में शेष सब इससे निकलता है कि अचक्रीयता की प्रत्याभूति पश्चात् परीक्षण के बजाय पहले चाही जाए, और द्वि-चरणीय तालन वही प्रोटोकॉल है जो देता है: कुछ भी छोड़ने से पूर्व अपने सब ताले लें, और कोई चक्र नहीं बन सकता।

अनुक्रमणिकाएँ: घनी, विरल, तथा कितनी प्राथमिक हो सकती हैं

अनुक्रमणिका की शब्दावली, तथा प्रत्येक प्रकार का प्रतिबंध
प्रकारउसका अर्थउससे निकलता प्रतिबंध
घनीप्रति खोज-कुंजी मान एक प्रविष्टिबड़ी अनुक्रमणिका, पर मान फ़ाइल स्पर्श किए बिना मिलता है
विरलआँकड़ा-फ़ाइल के प्रति खंड एक प्रविष्टिकेवल तब संभव जब फ़ाइल उस कुंजी पर क्रमित हो
प्राथमिक (गुच्छन)उस गुण पर बना जिससे फ़ाइल भौतिक रूप से क्रमित हैप्रति सारणी अधिकतम एक — फ़ाइल का एक भौतिक क्रम है
द्वितीयककिसी अन्य गुण पर बनाअनेक अनुमत, पर घनी होनी चाहिए — फ़ाइल उस क्रम में नहीं
🎯 द्वितीयक अनुक्रमणिका विरल क्यों नहीं हो सकती
विरल अनुक्रमणिका प्रति आँकड़ा-खंड एक प्रविष्टि संचित करती है और एक वचन पर निर्भर है: यदि आपका इच्छित मान अनुक्रमणिका में न हो, तो वह उन दो प्रविष्टियों के बीच है जो हैं, अतः आप पूर्ववर्ती सूचक का अनुसरण कर उस खंड के भीतर आगे क्रमवीक्षण करते हैं। वह वचन केवल तब सत्य है जब फ़ाइल अनुक्रमित कुंजी पर क्रमित हो। द्वितीयक अनुक्रमणिका ऐसे गुण पर बनी है जिससे फ़ाइल क्रमित नहीं है, अतः किसी दिए मान वाली पंक्तियाँ यादृच्छिक खंडों में बिखरी हैं और “यहाँ से आगे क्रमवीक्षण” जैसा कुछ नहीं — अतः प्रत्येक मान को अपनी प्रविष्टि चाहिए, और घनी का अर्थ वही है। दो परिणाम परीक्षित होते हैं। किसी सारणी में अधिकतम एक प्राथमिक (गुच्छन) अनुक्रमणिका हो सकती है, क्योंकि फ़ाइल का केवल एक भौतिक क्रम है, जबकि उसमें अनेक द्वितीयक अनुक्रमणिकाएँ हो सकती हैं। और उसी आँकड़े हेतु द्वितीयक अनुक्रमणिका बड़ी है और अनुरक्षण में मंद, जो दूसरे गुण को अनुक्रमित करने की ईमानदार लागत है।

B+ वृक्ष की कोटि एक असमिका है, तथ्य नहीं

कोई शीर्ष एक डिस्क खंड घेरता है, अतः उसकी कोटि वही है जो बैठती है। लें 1024-बाइट खंड, 10-बाइट खोज कुंजी व 8-बाइट सूचक। कोटि n का आंतरिक शीर्ष n सूचक व n − 1 कुंजियाँ रखता है, अतः प्रतिबंध है 8n + 10(n − 1) ≤ 1024, अर्थात् 18n ≤ 1034, जिससे n = 57। सीमा के दोनों ओर जाँचें, क्योंकि अंक वहीं खोए जाते हैं: n = 57 को 57(8) + 56(10) = 456 + 560 = 1016 बाइट चाहिए, जो बैठते हैं; n = 58 को 464 + 570 = 1034 चाहिए, जो नहीं। पर्ण भिन्न है: वह कुंजी–अभिलेख-सूचक युग्म तथा अगले पर्ण तक एक अतिरिक्त सूचक रखता है, अतः m(10 + 8) + 8 ≤ 1024, अर्थात् 18m ≤ 1016, जिससे m = 56। दोनों संख्याएँ एक से भिन्न हैं और संरचनात्मक कारण से — शृंखलन सूचक — अतः जो प्रश्न आपको दोनों दे और एक उत्तर की अपेक्षा करे वह जाँच रहा है कि आप जानते हैं आप कौन-से शीर्ष में हैं।

B वृक्ष बनाम B+ वृक्ष, प्रश्न वस्तुतः क्या पूछते हैं उस पर
पक्षB वृक्षB+ वृक्ष
आँकड़ा-सूचक कहाँ हैंप्रत्येक शीर्ष मेंकेवल पर्णों में
आंतरिक शीर्षों में कुंजियाँकम — प्रत्येक अभिलेख-सूचक भी रखती हैअधिक — आंतरिक कुंजियाँ शुद्ध विभाजक हैं
उसी आँकड़े हेतु ऊँचाईऊँचाछोटा, अतः कम खंड-पहुँचें
कोई कुंजी दो बार आ सकती हैनहीं — ठीक एक बारहाँ — एक बार विभाजक, एक बार पर्ण में
परिसर क्रमवीक्षणवृक्ष-भ्रमण चाहिएशृंखलित पर्णों पर चलें
एकल खोज हेतु सर्वोत्तम स्थितिमूल पर रुक सकता हैसदा पर्ण तक जाता है
⚠️ B+ वृक्ष औसत पर श्रेष्ठ और सर्वोत्तम स्थिति में निकृष्ट हैं
लगभग सब कुछ B+ वृक्ष के पक्ष में है — छोटी ऊँचाई, सस्ते परिसर-क्रमवीक्षण, एकरूप पर्ण-स्तरीय पहुँच — और ठीक एक स्थान है जहाँ B वृक्ष जीतता है, और इसीलिए वह विकल्प के रूप में आता है। B वृक्ष प्रत्येक शीर्ष में अभिलेख-सूचक संचित करता है, अतः ऐसी कुंजी की खोज जो संयोगवश मूल में बैठी हो एक खंड-पहुँच में समाप्त होती है। B+ वृक्ष पर्णों के ऊपर कोई आँकड़ा-सूचक नहीं रखता, अतः प्रत्येक खोज पूरी ऊँचाई उतरती है, कुंजी कितनी भी भाग्यशाली हो। अतः ईमानदार तुलना यह है: B+ वृक्षों की निकृष्टतम व औसत स्थिति श्रेष्ठ है और सर्वोत्तम स्थिति निकृष्ट, और कोई अभिलेख खोजने हेतु न्यूनतम खंड-पहुँचें पूछता प्रश्न ठीक उसी अंतर के विषय में पूछ रहा है। सौदा लेने योग्य होने का कारण यह है कि सर्वोत्तम स्थिति दस लाख में एक कुंजी है, जबकि ऊँचाई उन सब पर लागू है — और शृंखलित पर्ण “X व Y के बीच के सब अभिलेख” को बारंबार उतरने के बजाय क्रमिक चाल बना देते हैं, और आँकड़ाकोश वस्तुतः वही करने में समय व्यय करता है।

क्रमिकीकरणीयता एक चक्र-परीक्षण है

ACID गुणधर्म बताते हैं कि अभिलेन-देन क्या वचन देता है: अखंडता (सब या कुछ नहीं), संगति (सीमाओं पर प्रतिबंध टिकते हैं), एकांतता (परिणाम ऐसा है जैसे अन्य कोई चला ही नहीं), चिरस्थायित्व (प्रतिबद्ध परिवर्तन दुर्घटना में बचता है)। एकांतता वही है जिसके पीछे कोई कलनविधि है। दो संक्रियाएँ संघर्ष करती हैं जब वे उसी आँकड़ा-वस्तु को स्पर्श करें, भिन्न अभिलेन-देनों की हों, और कम से कम एक लेखन हो — अतः पठन–पठन कभी संघर्ष नहीं, और वही एक छूट सहवर्तिता को संभव ही बनाती है। पूर्वता ग्राफ बनाएँ: प्रति अभिलेन-देन एक शीर्ष, और किनारा Ti → Tj जब भी Ti की कोई संक्रिया Tj की पश्चात्वर्ती संक्रिया से संघर्ष करे। तत्पश्चात् प्रमेय: अनुसूची संघर्ष-क्रमिकीकरणीय है यदि और केवल यदि ग्राफ अचक्रीय हो, और अचक्रीय ग्राफ का कोई भी सांस्थितिक क्रम तुल्य क्रमिक अनुसूची है।

चार अनुसूचियाँ, प्रत्येक निर्णय उसके पूर्वता ग्राफ से पढ़ा गया
अनुसूचीकिनारेनिर्णय
R1(A) W2(A) R2(B) W1(B)T1→T2 (A पर), T2→T1 (B पर)चक्र — संघर्ष-क्रमिकीकरणीय नहीं
R1(A) R2(B) W1(A) W2(B)कोई नहीं — दोनों भिन्न वस्तुएँ स्पर्श करते हैंक्रमिकीकरणीय, किसी भी क्रम में
R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B)केवल T1→T2T1 < T2 के रूप में क्रमिकीकरणीय
R1(X) W2(X) W3(X) R1(Y) W3(Y)T1→T2, T1→T3, T2→T3T1 < T2 < T3 के रूप में क्रमिकीकरणीय
🧠 ग्राफ बनाएँ, अनुसूची को ताकें नहीं
प्रक्रिया परीक्षा-दबाव में करने योग्य पर्याप्त छोटी है और सब विवेक हटा देती है। एक: संक्रियाओं को क्रम में सूचीबद्ध करें। दो: भिन्न अभिलेन-देनों की उसी आँकड़ा-वस्तु पर प्रत्येक युग्म हेतु, जहाँ कम से कम एक लेखन हो, पूर्ववर्ती से पश्चात्वर्ती तक किनारा खींचें। तीन: चक्र खोजें। लें R1(A) W2(A) R2(B) W1(B)। A पर: R1(A) फिर W2(A) — पठन फिर लेखन, संघर्ष, अतः T1 → T2। B पर: R2(B) फिर W1(B) — पुनः पठन फिर लेखन, अतः T2 → T1। विपरीत दिशाओं में दो किनारे लंबाई दो का चक्र है, और अनुसूची संघर्ष-क्रमिकीकरणीय नहीं है। ध्यान दें इसे कितना कम चाहिए था: अभिलेन-देनों के अर्थ पर कोई तर्क नहीं, और तुल्य क्रमिक क्रम रचने व विफल होने का कोई प्रयास नहीं। सावधानी की एक बात दिशा है — किनारा सदा उस संक्रिया से चलता है जो पहले हुई, और उसे उलटना चक्र को वैध क्रम में बदल देता है व विलोमतः।
ℹ️ संघर्ष, दृश्य, तथा गिनती क्यों निकल आती है
संघर्ष-क्रमिकीकरणीयता पर्याप्त शर्त है, प्रत्येक सही अनुसूची का लक्षण नहीं। दृश्य-क्रमिकीकरणीय व्यापक वर्ग है: वह ऐसी अनुसूचियाँ भी स्वीकारता है जहाँ अंध लेखन — ऐसा लेखन जिससे पूर्व उस वस्तु का कोई पठन न हो — किसी प्रत्यक्षतः बुरे क्रम को हानिरहित बना देता है। अतः प्रत्येक संघर्ष-क्रमिकीकरणीय अनुसूची दृश्य-क्रमिकीकरणीय है, और विलोमतः नहीं, और व्यावहारिक पाठ यह है कि आँकड़ाकोश वस्तुतः संघर्ष-क्रमिकीकरणीयता लागू करता है क्योंकि अचक्रीयता जाँचना सस्ता है और दृश्य-क्रमिकीकरणीयता नहीं। गिनती पर, जो अपने प्रश्न-प्रकार के रूप में आती है: a व b संक्रियाओं वाले दो अभिलेन-देन कुल C(a+b, a) अंतर्वेशन स्वीकारते हैं, क्योंकि अनुसूची केवल यह चयन है कि कौन-सी स्थितियाँ प्रथम अभिलेन-देन की हैं। 2 व 2 संक्रियाओं हेतु वह C(4,2) = 6 है, जिनमें ठीक 2 क्रमिक; 3 व 3 हेतु C(6,3) = 20, तब भी केवल 2 क्रमिक। जो संख्या सूत्र नहीं है वह यह है कि उन अंतर्वेशनों में कितने क्रमिकीकरणीय हैं — वह इस पर निर्भर है कि संक्रियाएँ कौन-सी वस्तुएँ स्पर्श करती हैं, अतः उसे ग्राफ सहित अनुसूची-दर-अनुसूची जाँचना पड़ता है।

तालन: अचक्रीयता की प्रत्याभूति पहले से

तथ्य के पश्चात् ग्राफ जाँचना चालू आँकड़ाकोश हेतु अनुपयोगी है, जिसे अब तय करना है कि संक्रिया अनुमत करे या नहीं। द्वि-चरणीय तालन उसके स्थान पर क्रमिकीकरणीयता की प्रत्याभूति संरचनात्मक रूप से देता है। प्रत्येक अभिलेन-देन का एक वर्धमान चरण होता है, जिसमें वह ताले ले सकता है पर कोई छोड़ नहीं सकता, और एक संकुचित चरण, जिसमें वह छोड़ सकता है पर ले नहीं सकता — नियम सरलतः यह है कि एक बार कुछ छोड़ने के पश्चात् आप पुनः कभी ताला नहीं ले सकते। वही एक अनुशासन पूर्वता ग्राफ को अचक्रीय बना देता है, क्योंकि किसी अभिलेन-देन के अंतिम अर्जन का क्षण (उसका ताला-बिंदु) उन सब का संगत क्रम दे देता है।

प्रत्येक प्रोटोकॉल क्या प्रत्याभूत करता है, और क्या अभी भी नहीं
प्रोटोकॉलप्रत्याभूतिप्रत्याभूति नहीं
मूल 2PLसंघर्ष-क्रमिकीकरणीयतागतिरोध से मुक्ति; प्रत्युद्धरणीयता
कठोर 2PLक्रमिकीकरणीयता तथा अनुक्रम-रहित प्रत्युद्धरणगतिरोध से मुक्ति
अति-कठोर 2PLसब ताले प्रतिबद्धता तक धारित — तर्क करने में सरलतमगतिरोध से मुक्ति; अधिकतम सहवर्तिता
समय-चिह्न क्रमणक्रमिकीकरणीयता, तथा कभी गतिरोध नहींभुखमरी से मुक्ति — पुनरारंभित अभिलेन-देन भूखा रह सकता है
⚠️ 2PL अक्रमिकीकरणीयता रोकता है, गतिरोध नहीं
यही वह भेद है जिसकी परीक्षा हेतु खंड बना है। द्वि-चरणीय तालन प्रत्येक अनुमत अनुसूची को क्रमिकीकरणीय बनाता है, और गतिरोध के विषय में कुछ नहीं करता: T1, A पर ताला लगाकर B माँगता है जबकि T2, B पर ताला लगाकर A माँगता है, दोनों 2PL का पूर्ण पालन करते हुए, और दोनों सदा प्रतीक्षा करते हैं। आँकड़ाकोश उसे प्रतीक्षा-ग्राफ से संसूचित करता है और किसी शिकार को निरस्त करता है — और इसीलिए 2PL को कोई गतिरोध-रणनीति जोड़नी पड़ती है। रखने योग्य वैषम्य समय-चिह्न क्रमण है, जो रचना से कभी गतिरुद्ध नहीं होता, क्योंकि वह किसी अभिलेन-देन को प्रतीक्षा कराता ही नहीं: समय-चिह्न-क्रम से बाहर आती संक्रिया अस्वीकृत होती है और उसका अभिलेन-देन पुनरारंभ। अतः सौदा यह नहीं कि “कौन अधिक सुरक्षित” अपितु यह कि आप कौन-सी विफलता पसंद करते हैं — 2PL अवरुद्ध करता है और गतिरुद्ध हो सकता है, समय-चिह्न क्रमण निरस्त करता है और बारंबार पुनरारंभित अभिलेन-देन को भूखा रख सकता है। और स्वच्छ रखने योग्य एक और पृथक्करण: क्रमिकीकरणीयता परिणाम की शुद्धता के विषय में है, जबकि प्रत्युद्धरणीयता इसके विषय में कि दुर्घटना के पश्चात् क्या होता है। मूल 2PL पहला देता है और दूसरा नहीं; कठोर 2PL अनन्य ताले प्रतिबद्धता तक धारित रखता है, और वही अनुसूची को अनुक्रम-रहित बनाता है — कोई अभिलेन-देन ऐसा मान नहीं पढ़ता जो अप्रतिबद्ध द्वारा लिखा गया हो, अतः कोई निरसन अनुक्रमित नहीं हो सकता।

मुख्य बिंदु

  • द्वितीयक अनुक्रमणिका घनी होनी चाहिए; केवल क्रमित फ़ाइल विरल अनुक्रमणिका रख सकती है।
  • सारणी में अधिकतम एक प्राथमिक (गुच्छन) अनुक्रमणिका है, क्योंकि फ़ाइल का एक भौतिक क्रम है।
  • आंतरिक B+ कोटि 8n + 10(n−1) ≤ 1024 हल करती है → n = 57; पर्ण शृंखला-सूचक जोड़ता है → 56।
  • B वृक्ष खोज मूल पर समाप्त कर सकता है; B+ वृक्ष सदा पर्ण तक उतरता है।
  • दो संक्रियाएँ केवल उसी वस्तु पर कम से कम एक लेखन सहित संघर्ष करती हैं — पठन–पठन कभी नहीं।
  • संघर्ष-क्रमिकीकरणीय ठीक तब जब पूर्वता ग्राफ अचक्रीय हो; उसे बनाएँ, अनुमान न लगाएँ।
  • प्रत्येक संघर्ष-क्रमिकीकरणीय अनुसूची दृश्य-क्रमिकीकरणीय है; विलोम अंध लेखन पर विफल है।
  • a व b संक्रियाओं वाले दो अभिलेन-देन C(a+b, a) अंतर्वेशन स्वीकारते हैं, जिनमें केवल 2 क्रमिक।
  • 2PL क्रमिकीकरणीयता प्रत्याभूत करता है और गतिरोध-मुक्ति नहीं; समय-चिह्न क्रमण उलटा है।
  • कठोर 2PL अनन्य ताले प्रतिबद्धता तक रखता है, और वही अनुसूची को अनुक्रम-रहित बनाता है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. कोई B+ वृक्ष अनुक्रमणिका 1024 बाइट के डिस्क खंड, 10 बाइट के खोज-कुंजी मान व 8 बाइट के खंड-सूचक प्रयोग करती है। किसी आंतरिक शीर्ष की अधिकतम कोटि (खंड-सूचकों की संख्या) ______ है

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 57

    57। कोटि n का आंतरिक शीर्ष n खंड-सूचक व n − 1 कुंजियाँ रखता है — सूचक से एक कम कुंजी, क्योंकि कुंजियाँ सूचकों के बीच बैठते विभाजक हैं। अतः आवश्यक स्थान 8n + 10(n − 1) ≤ 1024 है, जो 18n − 10 ≤ 1024 है, अतः 18n ≤ 1034 और n ≤ 57.44। कोटि पूर्णांक होनी चाहिए, अतः n = 57। सीमा के दोनों ओर जाँचें, जहाँ यह प्रश्न प्रायः खोया जाता है: n = 57 को 57(8) + 56(10) = 456 + 560 = 1016 बाइट चाहिए और 8 बचाकर बैठता है; n = 58 को 464 + 570 = 1034 चाहिए, दस बाइट अधिक। दो सामान्य गलत उत्तर नाम लेने योग्य हैं। 58, 57.44 को नीचे के बजाय ऊपर पूर्णांकित करने से आता है — असमिका क्षमता-सीमा है, अतः वह सदा नीचे पूर्णांकित होती है। और 56 पर्ण की कोटि है, जो भिन्न गणना है: पर्ण कुंजी–अभिलेख-सूचक युग्म तथा अगले पर्ण तक एक अतिरिक्त सूचक रखता है, जिससे 18m + 8 ≤ 1024 और m = 56।

  2. अनुसूची R1(A) W2(A) R2(B) W1(B) पर विचार करें। कौन-सा कथन सही है?

    1. वह संघर्ष-क्रमिकीकरणीय है, T1 < T2 के तुल्य
    2. वह संघर्ष-क्रमिकीकरणीय नहीं, क्योंकि पूर्वता ग्राफ में चक्र है
    3. वह संघर्ष-क्रमिकीकरणीय है, T2 < T1 के तुल्य
    4. वह क्रमिक है
    उत्तर देखें

    उत्तर: B — वह संघर्ष-क्रमिकीकरणीय नहीं, क्योंकि पूर्वता ग्राफ में चक्र है

    संघर्ष-क्रमिकीकरणीय नहीं। ग्राफ यांत्रिक रूप से बनाएँ। वस्तु A पर: R1(A), W2(A) से पूर्व आता है, भिन्न अभिलेन-देन, और एक लेखन है, अतः वह संघर्ष है और किनारा पूर्ववर्ती संक्रिया से चलता है — T1 → T2। वस्तु B पर: R2(B), W1(B) से पूर्व आता है, पुनः पठन के पश्चात् लेखन, अतः T2 → T1। विपरीत दिशाओं में दो किनारे लंबाई दो का चक्र बनाते हैं, और प्रमेय से अनुसूची संघर्ष-क्रमिकीकरणीय नहीं — T1 व T2 का कोई क्रमिक क्रम वही परिणाम नहीं देता, और इसीलिए विकल्प A व C दोनों गलत हैं, उनमें एक नहीं। विकल्प D अंतर्वेशन को क्रमिकता से भ्रमित करता है: क्रमिक अनुसूची दूसरे के किसी भाग से पूर्व एक अभिलेन-देन का सब चलाती है, और यहाँ संक्रियाएँ एकांतरित हैं। यह अनुसूची प्रामाणिक उदाहरण होने का संरचनात्मक कारण: प्रत्येक अभिलेन-देन एक वस्तु पढ़ता व दूसरी लिखता है, अतः प्रत्येक को दूसरे से पूर्व होना चाहिए, और अक्रमिकीकरणीय अंतर्वेशन का आकार ठीक वही है।

  3. द्वि-चरणीय तालन (2PL) क्या प्रत्याभूत करता है?

    1. क्रमिकीकरणीयता व गतिरोध से मुक्ति
    2. क्रमिकीकरणीयता, किंतु गतिरोध अभी भी संभव
    3. गतिरोध से मुक्ति, किंतु क्रमिकीकरणीयता नहीं
    4. समय-चिह्न क्रमण जोड़े बिना कोई नहीं
    उत्तर देखें

    उत्तर: B — क्रमिकीकरणीयता, किंतु गतिरोध अभी भी संभव

    क्रमिकीकरणीयता, किंतु गतिरोध अभी भी संभव — और प्रति-उदाहरण दो पंक्ति लंबा है। T1, A पर ताला लगाकर B माँगता है; T2, B पर ताला लगाकर A माँगता है। दोनों अपने वर्धमान चरण में हैं, अतः दोनों 2PL का पूर्ण पालन करते हैं, और दोनों परस्पर सदा प्रतीक्षा करते हैं। 2PL उस क्रम पर प्रतिबंध लगाता है जिसमें अभिलेन-देन ताले लेता व छोड़ता है, जो पूर्वता ग्राफ को अचक्रीय और अतः अनुसूची को क्रमिकीकरणीय बनाने हेतु पर्याप्त है, पर वह इस विषय में कुछ नहीं कहता कि निवेदन संतुष्ट हो सकते हैं क्या। अतः आँकड़ाकोश कोई गतिरोध-रणनीति जोड़ता है: प्रतीक्षा-ग्राफ तथा शिकार-चयन, या कोई समय-सीमा। शिक्षाप्रद वैषम्य समय-चिह्न क्रमण है, जो रचना से गतिरोध-मुक्त है क्योंकि वह किसी को प्रतीक्षा कराता ही नहीं — क्रम-बाह्य संक्रिया अस्वीकृत होती है और उसका अभिलेन-देन पुनरारंभ — और जो उसका मूल्य ऐसे अभिलेन-देन की संभावित भुखमरी से चुकाता है जो बारंबार पुनरारंभित होता रहे। विकल्प C प्रत्याभूति पूर्णतः उलट देता है। विकल्प D मुख्य बिंदु पर गलत है: केवल 2PL क्रमिकीकरणीयता हेतु पर्याप्त है, और ठीक इसीलिए वह मानक प्रोटोकॉल है।

  4. अभिलेन-देन T1 की 3 संक्रियाएँ हैं और T2 की 3। प्रत्येक अभिलेन-देन का आंतरिक क्रम संरक्षित रखते हुए, संभावित अनुसूचियों की कुल संख्या ______ है

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 20

    20। अनुसूची पूर्णतः इससे निर्धारित है कि कौन-सी स्थितियाँ T1 की हैं, क्योंकि प्रत्येक अभिलेन-देन की संक्रियाओं को अपने क्रम में रहना चाहिए — एक बार जान लें कि T1 के पास, मानें, स्थिति 1, 3 व 4 हैं, तो शेष सब बाध्य है। अतः गिनती 6 में से 3 स्थितियाँ चुनने के तरीकों की संख्या है, जो C(6, 3) = 20 है। सामान्यतः a व b संक्रियाओं वाले दो अभिलेन-देन C(a + b, a) अनुसूचियाँ स्वीकारते हैं। उन 20 में ठीक 2 क्रमिक हैं — T1 का सब फिर T2 का सब, या विलोम — और वह गिनती संक्रिया-संख्याओं से निरपेक्ष सदा 2 है, जो उपयोगी जाँच है। ध्यान दें प्रश्न क्या नहीं पूछता, क्योंकि वह भिन्न व कठिनतर प्रश्न है: उन 20 में कितने क्रमिकीकरणीय हैं यह इस पर निर्भर है कि संक्रियाएँ कौन-सी आँकड़ा-वस्तुएँ स्पर्श करती हैं और उसका कोई सूत्र नहीं, अतः उसे पूर्वता ग्राफ सहित अनुसूची-दर-अनुसूची तय करना पड़ता है। सामान्य गलत उत्तर 6! = 720 है, जो सब छह संक्रियाओं को स्वतंत्र रूप से क्रमचयित करने और यह अवहेलना करने से आता है कि प्रत्येक अभिलेन-देन का आंतरिक क्रम नियत है।

  5. उसी आँकड़े को रखते B वृक्षों की तुलना में B+ वृक्षों के विषय में निम्नलिखित में से कौन-से सत्य हैं?

    1. B+ वृक्ष का आंतरिक शीर्ष अधिक कुंजियाँ रख सकता है, अतः वृक्ष छोटा है
    2. परिसर पृच्छा सस्ती है, क्योंकि पर्ण शृंखलित हैं
    3. B+ वृक्ष में प्रत्येक खोज पर्ण तक पहुँचती है
    4. एकल-अभिलेख खोज हेतु खंड-पहुँचों की न्यूनतम संख्या B+ वृक्ष में कम है
    उत्तर देखें

    उत्तर: A — B+ वृक्ष का आंतरिक शीर्ष अधिक कुंजियाँ रख सकता है, अतः वृक्ष छोटा है; B — परिसर पृच्छा सस्ती है, क्योंकि पर्ण शृंखलित हैं; C — B+ वृक्ष में प्रत्येक खोज पर्ण तक पहुँचती है

    A, B व C। A संरचनात्मक लाभ है: B+ वृक्ष अभिलेख-सूचक केवल पर्णों में रखता है, अतः आंतरिक शीर्ष अपना सम्पूर्ण खंड विभाजक कुंजियों व संतान-सूचकों पर व्यय करता है और अतः अधिक चौड़ा फैलता है — अधिक चौड़ा फैलाव उतने ही अभिलेखों हेतु कम स्तरों का अर्थ है। B पर्ण-शृंखलन से निकलता है: प्रथम अर्ह अभिलेख मिलने पर शेष परिसर प्रति कुंजी नए अवतरण के बजाय नीचे के साथ क्रमिक चाल है। C सत्य है और वही कारण है जिससे D असत्य है, और वही एक विकल्प ठहरने योग्य है। चूँकि पर्ण-स्तर के ऊपर कोई आँकड़ा-सूचक नहीं बैठता, प्रत्येक खोज को पूरी ऊँचाई उतरना पड़ता है, अतः B+ वृक्ष खोज का न्यूनतम उसकी ऊँचाई के बराबर है। B वृक्ष प्रत्येक शीर्ष में अभिलेख-सूचक संचित करता है, अतः संयोगवश मूल में बैठी कुंजी एक खंड-पहुँच में मिल जाती है — निम्नतर न्यूनतम। अतः ईमानदार सार यह है कि B+ वृक्ष निकृष्टतम व औसत स्थिति पर जीतते हैं और सर्वोत्तम स्थिति पर हारते हैं, और न्यूनतम पूछता प्रश्न ठीक उसी के विषय में पूछ रहा है।

  6. किसी अक्रमक गुण पर द्वितीयक अनुक्रमणिका विरल के बजाय घनी होनी चाहिए। क्यों?

    1. क्योंकि द्वितीयक अनुक्रमणिकाएँ परिपाटी से सदा बड़ी होती हैं
    2. क्योंकि फ़ाइल उस गुण पर क्रमित नहीं, अतः भीतर आगे क्रमवीक्षण करने योग्य कोई खंड नहीं
    3. क्योंकि विरल अनुक्रमणिका सूचक संचित नहीं कर सकती
    4. क्योंकि द्वितीयक अनुक्रमणिकाएँ मुख्य स्मृति में संचित होती हैं
    उत्तर देखें

    उत्तर: B — क्योंकि फ़ाइल उस गुण पर क्रमित नहीं, अतः भीतर आगे क्रमवीक्षण करने योग्य कोई खंड नहीं

    विरल अनुक्रमणिका प्रति आँकड़ा-खंड एक प्रविष्टि रखती है और एक वचन से काम करती है: अनुक्रमणिका में न आया मान उन दो के बीच है जो हैं, अतः आप पूर्ववर्ती सूचक का अनुसरण करके उस खंड के भीतर आगे क्रमवीक्षण करते हैं जब तक वह मिले। वह वचन पूर्णतः इस पर निर्भर है कि फ़ाइल अनुक्रमित गुण पर क्रमित हो। द्वितीयक अनुक्रमणिका ऐसे गुण पर बनी है जिससे फ़ाइल क्रमित नहीं है, अतः कोई मान साझा करती पंक्तियाँ यादृच्छिक खंडों में बिखरी हैं और क्रमवीक्षण योग्य कोई अर्थपूर्ण “आगे” नहीं — अतः प्रत्येक मान को अपनी प्रविष्टि चाहिए, और घनी का अर्थ वही है। विकल्प A परिणाम बताकर उसे कारण कहता है; अनुक्रमणिका बड़ी है क्योंकि उसे घनी होना चाहिए। विकल्प C सरलतः असत्य है — प्रत्येक अनुक्रमणिका सूचक संचित करती है। विकल्प D परिभाषा का अंग नहीं और वैसे भी समस्या नहीं सुधारता। इसके साथ जोड़ने योग्य सहचर तथ्य: किसी सारणी में अधिकतम एक प्राथमिक (गुच्छन) अनुक्रमणिका हो सकती है, चूँकि फ़ाइल का एक भौतिक क्रम है, पर उतनी द्वितीयक अनुक्रमणिकाएँ जितनी आप अनुरक्षित करने को तैयार हों।

  7. तीन अभिलेन-देनों की किसी अनुसूची के पूर्वता-ग्राफ किनारे T1 → T2, T1 → T3 व T2 → T3 हैं। अनुसूची है:

    1. संघर्ष-क्रमिकीकरणीय नहीं, क्योंकि तीन शीर्षों में तीन किनारे चक्र बाध्य करते हैं
    2. संघर्ष-क्रमिकीकरणीय, क्रमिक क्रम T1 < T2 < T3 के तुल्य
    3. संघर्ष-क्रमिकीकरणीय, तीन भिन्न तुल्य क्रमिक क्रमों सहित
    4. क्रमिकीकरणीय केवल तब यदि T2 व T3 भिन्न आँकड़ा-वस्तुएँ स्पर्श करें
    उत्तर देखें

    उत्तर: B — संघर्ष-क्रमिकीकरणीय, क्रमिक क्रम T1 < T2 < T3 के तुल्य

    संघर्ष-क्रमिकीकरणीय, और T1 < T2 < T3 क्रम है। चक्र जाँचें: प्रत्येक किनारा निम्न-क्रमांक अभिलेन-देन से उच्च-क्रमांक की ओर संकेत करता है, अतः किनारों का अनुसरण केवल आगे बढ़ सकता है और कोई पथ आरंभ-स्थान पर नहीं लौट सकता — ग्राफ अचक्रीय है। प्रमेय से अनुसूची संघर्ष-क्रमिकीकरणीय है, और तुल्य क्रमिक क्रम ग्राफ का कोई भी सांस्थितिक क्रमण है। यहाँ क्रमण अद्वितीय है: T1 को दोनों से पूर्व होना चाहिए, और T2 को T3 से पूर्व, जिससे ठीक एक व्यवस्था बचती है। विकल्प A किनारों की गिनती को चक्र का साक्ष्य मानता है, पर तीन शीर्ष बिना किसी चक्र के तीन किनारे तक रख सकते हैं — यह ग्राफ ठीक वही स्थिति है, और उसे दिशा तय करती है, गिनती नहीं। विकल्प C हेतु सांस्थितिक क्रम अस्पष्ट चाहिए, जो तब होता है जब कोई युग्म अप्रतिबंधित हो; यहाँ प्रत्येक युग्म का किनारा है। विकल्प D ऐसी शर्त जोड़ता है जिसे ग्राफ पहले ही तय कर चुका है — किनारा T2 → T3 विद्यमान है, अतः वे संघर्ष करते हैं, और अनुसूची तब भी क्रमिकीकरणीय है।

  8. कठोर 2PL, मूल 2PL के ऊपर कौन-सा गुणधर्म जोड़ता है?

    1. गतिरोध से मुक्ति
    2. अनुक्रम-रहित प्रत्युद्धरण, प्रतिबद्धता तक अनन्य ताले धारित रखकर
    3. उच्चतर सहवर्तिता
    4. संघर्ष-क्रमिकीकरणीयता के स्थान पर दृश्य-क्रमिकीकरणीयता
    उत्तर देखें

    उत्तर: B — अनुक्रम-रहित प्रत्युद्धरण, प्रतिबद्धता तक अनन्य ताले धारित रखकर

    अनुक्रम-रहित प्रत्युद्धरण। मूल 2PL पहले ही क्रमिकीकरणीयता देता है, अतः कठोर 2PL परिणाम की शुद्धता नहीं जोड़ रहा — वह दुर्घटना-प्रत्युद्धरण के विषय में कुछ जोड़ रहा है, जो पृथक् चिंता है। प्रत्येक अनन्य ताले को अभिलेन-देन की प्रतिबद्धता तक धारित रखकर कठोर 2PL प्रत्याभूत करता है कि कोई अभिलेन-देन ऐसा मान कभी नहीं पढ़ता जो अभी अप्रतिबद्ध द्वारा लिखा गया हो। अनुक्रम-रहित अनुसूची की शर्त ठीक वही है: चूँकि कोई अप्रतिबद्ध आँकड़े पर निर्भर नहीं था, किसी अभिलेन-देन को निरस्त करना अन्य अभिलेन-देनों को उसके साथ निरस्त होने को बाध्य नहीं कर सकता। विकल्प A मानक गलत उत्तर है और भेद तीक्ष्ण रखने योग्य है — 2PL का कोई प्रकार गतिरोध नहीं रोकता, क्योंकि ताले अधिक देर रखना गतिरोध को अधिक संभाव्य बनाता है, कम नहीं। विकल्प C उसी कारण से उलटा है: प्रतिबद्धता तक धारित ताले सहवर्तिता घटाते हैं, और वही कमी अनुक्रम-रहितता का चुकाया मूल्य है। विकल्प D दो भिन्न अनुक्रमों को भ्रमित करता है; 2PL प्रत्येक प्रकार में संघर्ष-क्रमिकीकरणीयता लागू करता है, और दृश्य-क्रमिकीकरणीयता व्यापक वर्ग है जिसे कोई तालन प्रोटोकॉल लक्ष्य नहीं करता।