विदेशी डेटा संरचनाएं: संशोधित मर्कल पेट्रीसिया ट्राइ

"मुझे इन सभी लघुरूप एल्गोरिदम और डेटा संरचनाओं को किस तरह के शैतान को दिल से याद करना चाहिए?"

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

मिस्टीरियस मॉडिफाइड मर्कल पेट्रीसिया ट्राई।

चूँकि इस पेड़ के बारे में कोई जानकारी नहीं है, क्योंकि यह हब्र और मीडियम में है - थोड़ा और, मैं आपको बताना चाहता हूं कि यह किस तरह का जानवर है और इसके साथ क्या खाया जाता है।

यह क्या है

डिस्क्लेमर: मेरे लिए कार्यान्वयन के लिए सूचना का मुख्य स्रोत येलो पेपर था, साथ ही स्रोत कोड समता-इथेरियम और गो-एथेरियम था । कुछ निर्णयों के औचित्य पर न्यूनतम सैद्धांतिक जानकारी थी, इसलिए कुछ निर्णय लेने के कारणों के बारे में सभी निष्कर्ष मेरे व्यक्तिगत हैं। मामले में मुझे कुछ गलत लगता है - मुझे टिप्पणियों में सुधार करने में खुशी होगी।

एक पेड़ एक डेटा संरचना है जो एक जुड़ा हुआ चक्रीय ग्राफ है। यहां सब कुछ सरल है, हर कोई इससे परिचित है।

उपसर्ग वृक्ष रूट ट्री है जिसमें की-वैल्यू पेयर को इस तथ्य के कारण संग्रहित किया जा सकता है कि नोड्स को दो प्रकारों में विभाजित किया गया है: वे जिनमें पथ (उपसर्ग) का हिस्सा होता है, और पत्ती नोड्स जिसमें संग्रहीत मूल्य होता है। एक मूल्य एक पेड़ में मौजूद है यदि और केवल यदि, कुंजी का उपयोग करके, हम पेड़ की जड़ से सभी तरह से जा सकते हैं और अंत में एक मूल्य के साथ एक नोड ढूंढ सकते हैं।

PATRICIA पेड़ एक उपसर्ग वृक्ष है जिसमें उपसर्ग द्विआधारी होते हैं - अर्थात, प्रत्येक कुंजी नोड एक बिट के बारे में जानकारी संग्रहीत करता है।

मर्कल ट्री एक हैश ट्री है जो किसी प्रकार की डेटा श्रृंखला के ऊपर बनाया गया है, इन सभी हैश को एक (मूल) में मिलाकर, सभी डेटा ब्लॉक की स्थिति के बारे में जानकारी संग्रहीत करता है। यही है, रूट हैश ब्लॉक श्रृंखला की स्थिति का एक प्रकार का "डिजिटल हस्ताक्षर" है। ब्लॉकचेन में इस चीज का सक्रिय रूप से उपयोग किया जाता है, और इसके बारे में अधिक जानकारी यहां पाई जा सकती है ।

कुल: संशोधित मर्कल पेट्रीसिया ट्राइ (बाद में एमपीटी शॉर्ट के लिए) एक हैश ट्री है जो की-वैल्यू पेयर को स्टोर करता है, और कुंजियों को बाइनरी रूप में प्रस्तुत किया जाता है। और वास्तव में "संशोधित" के बारे में क्या है, हम कार्यान्वयन के बारे में चर्चा करने पर थोड़ा बाद में पता लगाएंगे।

यह क्यों है?

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

इथेरियम डेवलपर्स द्वारा सामना की जाने वाली मुख्य समस्या एक डेटा संरचना का निर्माण है जो प्रभावी रूप से कुंजी-मूल्य जोड़े को संग्रहीत कर सकती है और साथ ही संग्रहीत डेटा का सत्यापन प्रदान करती है। तो एमपीटी दिखाई दिया।

वह कैसे है?

एमपीटी एक उपसर्ग PATRICIA पेड़ है जिसमें कुंजियाँ बाइट्स के अनुक्रम हैं।

इस पेड़ के किनारों को कुतरने के क्रम (आधे बाइट्स) हैं। तदनुसार, एक नोड में सोलह वंशज (0x0 से 0xF तक की शाखाओं के अनुरूप) हो सकते हैं।

नोड्स को 3 प्रकारों में विभाजित किया जाता है:

• शाखा नोड। ब्रांचिंग के लिए प्रयुक्त नोड। बच्चे के नोड्स में 1 से 16 लिंक शामिल हैं। एक मान भी हो सकता है।
• एक्सटेंशन नोड। एक सहायक नोड जो पथ के कुछ हिस्से को कई बच्चे नोड्स के लिए आम तौर पर संग्रहीत करता है, साथ ही शाखा नोड का लिंक भी है, जो नीचे स्थित है।
• पत्ती का नोड। पथ और संग्रहीत मान का एक हिस्सा युक्त नोड। यह श्रृंखला में अंत है।

जैसा कि पहले ही उल्लेख किया गया है, एमपीटी एक अन्य केवी रिपॉजिटरी के शीर्ष पर बनाया गया है, जो नोड्स को "लिंक" => " RLP एनकोडेड नोड" के रूप में संग्रहीत करता है।

और यहां हम एक नई अवधारणा लेकर आए हैं: आरएलपी। संक्षेप में, यह सूचियों या बाइट अनुक्रमों का प्रतिनिधित्व करने वाले डेटा को एन्कोडिंग करने की एक विधि है। उदाहरण: [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ] । मैं विशेष रूप से विवरण में नहीं जाऊंगा, और कार्यान्वयन में मैं एक तैयार पुस्तकालय का उपयोग करता हूं, क्योंकि इस विषय का कवरेज भी पहले से ही बल्कि बड़े लेख को बढ़ाएगा। यदि आप अभी भी रुचि रखते हैं, तो आप यहां और अधिक पढ़ सकते हैं। हम खुद को इस तथ्य तक सीमित करते हैं कि हम RLP में डेटा को एनकोड कर सकते हैं और इसे वापस डिकोड कर सकते हैं।

नोड का लिंक निम्नानुसार परिभाषित किया गया है: यदि RLP एन्कोडेड नोड की लंबाई 32 या अधिक बाइट्स है, तो लिंक नोड के keccak प्रतिनिधित्व से एक keccak हैश है। यदि लंबाई 32 बाइट्स से कम है, तो लिंक नोड का RLP प्रतिनिधित्व है।

जाहिर है, दूसरे मामले में, आपको नोड को डेटाबेस में सहेजने की आवश्यकता नहीं है, क्योंकि यह पूरी तरह से मूल नोड के अंदर सहेजा जाएगा।

तीन प्रकार के नोड्स का संयोजन आपको उस मामले में प्रभावी रूप से डेटा संग्रहीत करने की अनुमति देता है जब कुछ चाबियाँ होती हैं (तब अधिकांश पथ विस्तार और पत्ती नोड्स में संग्रहीत किए जाएंगे, और कुछ शाखा नोड्स होंगे), और मामले में जब कई नोड्स (पथ स्पष्ट रूप से संग्रहीत नहीं होंगे) लेकिन वे शाखा नोड्स के माध्यम से पारित होने के दौरान "इकट्ठा" करेंगे।

सभी प्रकार के नोड्स का उपयोग करते हुए एक पेड़ का पूरा उदाहरण:

जैसा कि आपने देखा होगा, रास्तों के संग्रहित भागों में उपसर्ग होते हैं। कई उद्देश्यों के लिए उपसर्ग आवश्यक हैं:

1. पत्ती नोड्स से विस्तार नोड्स को भेद करने के लिए।
2. विषम संख्या में निबल्स के अनुक्रम संरेखित करना।

उपसर्ग बनाने के नियम बहुत सरल हैं:

• उपसर्ग 1 कुतरना लेता है। यदि पथ की लंबाई (उपसर्ग को छोड़कर) विषम है, तो पथ उपसर्ग के तुरंत बाद शुरू होता है। यदि पथ की लंबाई समान है, तो उपसर्ग के बाद संरेखित करने के लिए, निबल 0x0 पहले जोड़ा जाता है।
• उपसर्ग शुरू में 0x0 है।
• यदि पथ की लंबाई विषम है, तो 0x1 को उपसर्ग में जोड़ा जाता है, यदि - 0x0 भी।
• यदि पथ लीफ नोड की ओर जाता है, तो 0x2 को उपसर्ग में जोड़ा जाता है, यदि 0x0 को एक्सटेंशन नोड में जोड़ा जाता है।

बीटिक्स पर, मुझे लगता है कि यह स्पष्ट हो जाएगा:

 0b0000 =>  , Extension  0b0001 =>  , Extension  0b0010 =>  , Leaf  0b0011 =>  , Leaf  

विलोपन जो विलोपन नहीं है

इस तथ्य के बावजूद कि पेड़ में नोड्स को हटाने का संचालन होता है, वास्तव में, जो कुछ एक बार जोड़ा गया था वह हमेशा के लिए पेड़ में रहता है।

यह प्रत्येक ब्लॉक के लिए एक पूर्ण पेड़ नहीं बनाने के लिए आवश्यक है, लेकिन केवल पेड़ के पुराने और नए संस्करणों के बीच अंतर को स्टोर करने के लिए।

तदनुसार, एंट्री पॉइंट के रूप में अलग-अलग रूट हैश का उपयोग करके, हम उन राज्यों में से किसी को भी प्राप्त कर सकते हैं जो पेड़ कभी अंदर रहे हैं।

ये सभी अनुकूलन नहीं हैं। अधिक है, लेकिन हम इसके बारे में बात नहीं करेंगे - और इसलिए लेख बड़ा है। हालाँकि, आप अपने लिए पढ़ सकते हैं ।

कार्यान्वयन

सिद्धांत खत्म हो गया है, चलो अभ्यास करने के लिए आगे बढ़ें। हम आईटी दुनिया से लिंगुआ फ्रेंका का उपयोग करेंगे, वह python ।

चूंकि बहुत सारे कोड होंगे, और लेख के प्रारूप के लिए, बहुत कुछ कम करना होगा और विभाजित करना होगा, मैं तुरंत जीथब का लिंक छोड़ दूंगा।
यदि आवश्यक हो, तो आप पूरी तस्वीर देख सकते हैं।

सबसे पहले, हम ट्री इंटरफ़ेस को परिभाषित करते हैं जिसे हम परिणाम के रूप में प्राप्त करना चाहते हैं:

 class MerklePatriciaTrie: def __init__(self, storage, root=None): pass def root(self): pass def get(self, encoded_key): pass def update(self, encoded_key, encoded_value): pass def delete(self, encoded_key): pass 

इंटरफ़ेस बेहद सरल है। उपलब्ध परिचालन, रूट हैश को प्राप्त करने, हटाने, सम्मिलित करने और बदलने (अपडेट में) शामिल हैं।

भंडारण को __init__ विधि में स्थानांतरित किया जाएगा - एक dict तरह डेटा संरचना जिसमें हम नोड्स, साथ ही root - पेड़ के "शीर्ष" को संग्रहीत करेंगे। यदि None को root रूप में पारित None किया जाता root , तो हम मानते हैं कि पेड़ खाली है और खरोंच से काम करता है।

_REDIA: आप सोच रहे होंगे कि तरीकों में चर को encoded_key और encoded_value रूप में क्यों नामित किया गया है, न कि केवल key / value । उत्तर सरल है: विनिर्देश के अनुसार, सभी कुंजियों और मूल्यों को RLP में एन्कोड किया जाना चाहिए। हम खुद को इससे परेशान नहीं करेंगे और लाइब्रेरी उपयोगकर्ताओं के कंधों पर इस कब्जे को छोड़ देंगे ।_

हालांकि, इससे पहले कि हम खुद पेड़ को लागू करना शुरू कर दें, दो महत्वपूर्ण चीजें होनी चाहिए:

1. NibblePath क्लास को लागू करें, जो निबल्स की एक श्रृंखला है, ताकि उन्हें मैन्युअल रूप से एनकोड न किया जा सके।
2. इस वर्ग के ढांचे के भीतर Node वर्ग को लागू करने के लिए - Extension , Leaf और Branch ।

NibblePath

तो, NibblePath । चूंकि हम सक्रिय रूप से पेड़ के चारों ओर घूमेंगे, इसलिए हमारी कक्षा की कार्यक्षमता का आधार पथ की शुरुआत से "ऑफसेट" सेट करने की क्षमता होनी चाहिए, साथ ही साथ एक विशिष्ट कुतरना प्राप्त करना होगा। यह जानकर, हम अपनी कक्षा के आधार को परिभाषित करते हैं (साथ ही नीचे दिए गए उपसर्गों के साथ काम करने के लिए कुछ उपयोगी स्थिरांक):

 class NibblePath: ODD_FLAG = 0x10 LEAF_FLAG = 0x20 def __init__(self, data, offset=0): self._data = data # ,   . self._offset = offset #      def consume(self, amount): # "" N      . self._offset += amount return self def at(self, idx): #      idx = idx + self._offset #    ,   ,    , #   ,    -      . byte_idx = idx // 2 nibble_idx = idx % 2 #   . byte = self._data[byte_idx] #      . nibble = byte >> 4 if nibble_idx == 0 else byte & 0x0F return nibble 

काफी आसान है, है ना?

यह निबल्स के अनुक्रम को एन्कोडिंग और डिकोड करने के लिए केवल फ़ंक्शन लिखने के लिए रहता है।

 class NibblePath: # ... def decode_with_type(data): #   : # ,     ,    . is_odd_len = data[0] & NibblePath.ODD_FLAG == NibblePath.ODD_FLAG is_leaf = data[0] & NibblePath.LEAF_FLAG == NibblePath.LEAF_FLAG #    ,     #    . offset  , #       "" . offset = 1 if is_odd_len else 2 return NibblePath(data, offset), is_leaf def encode(self, is_leaf): output = [] #    ,       . nibbles_len = len(self._data) * 2 - self._offset is_odd = nibbles_len % 2 == 1 #  . prefix = 0x00 #    ,    . #      (self.at(0))     . #           (0x0). prefix += self.ODD_FLAG + self.at(0) if is_odd else 0x00 #  ,  Leaf node,  . prefix += self.LEAF_FLAG if is_leaf else 0x00 output.append(prefix) # ,      ,  . pos = nibbles_len % 2 #          , #     2 ,    , #     , #    . while pos < nibbles_len: byte = self.at(pos) * 16 + self.at(pos + 1) output.append(byte) pos += 2 return bytes(output) 

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

नोड

जैसा कि हम पहले से ही जानते हैं, हमारे नोड्स को तीन प्रकारों में विभाजित किया जाता है: लीफ, एक्सटेंशन और ब्रांच। उन सभी को एन्कोड और डिकोड किया जा सकता है, और अंतर केवल वह डेटा है जो अंदर संग्रहीत है। ईमानदार होने के लिए, यह बीजीय डेटा प्रकारों के लिए कहा जाता है, और Rust , उदाहरण के लिए, मैं आत्मा में कुछ लिखूंगा:

 pub enum Node<'a> { Leaf(NibblesSlice<'a>, &'a [u8]), Extension(NibblesSlice<'a>, NodeReference), Branch([Option<NodeReference>; 16], Option<&'a [u8]>), } 

हालांकि, अजगर में कोई एडीटी नहीं है, इसलिए हम Node वर्ग को परिभाषित करेंगे, और इसके अंदर नोड प्रकार के अनुरूप तीन कक्षाएं हैं। हम नोड कक्षाओं में सीधे कोडिंग को लागू करते हैं, और Node वर्ग में डिकोडिंग करते हैं।

कार्यान्वयन, हालांकि, प्राथमिक है:

पत्ता:

 class Leaf: def __init__(self, path, data): self.path = path self.data = data def encode(self): #    --    , #   -  ,   -  . return rlp.encode([self.path.encode(True), self.data]) 

एक्सटेंशन:

 class Extension: def __init__(self, path, next_ref): self.path = path self.next_ref = next_ref def encode(self): #    --    , #   -  ,   -    . next_ref = _prepare_reference_for_encoding(self.next_ref) return rlp.encode([self.path.encode(False), next_ref]) 

शाखा:

 class Branch: def __init__(self, branches, data=None): self.branches = branches self.data = data def encode(self): #    --    ,  #  16 -     (  ), #   -   (  ). branches = list(map(_prepare_reference_for_encoding, self.branches)) return rlp.encode(branches + [self.data]) 

सब कुछ बहुत सरल है। केवल एक चीज जो प्रश्न पैदा कर सकती है वह है _prepare_reference_for_encoding फ़ंक्शन।

फिर मैं स्वीकार करता हूं, मुझे एक छोटी बैसाखी का उपयोग करना था। तथ्य यह है कि उपयोग की गई rlp लाइब्रेरी डेटा को पुनरावर्ती rlp डिकोड करती है, और दूसरे नोड का लिंक, जैसा कि हम जानते हैं, rlp डेटा हो सकता है (यदि एन्कोडेड नोड 32 वर्णों से कम लंबा है)। दो स्वरूपों में लिंक के साथ काम करना - हैश बाइट्स और एक डिकोडेड नोड - बहुत असुविधाजनक है। इसलिए, मैंने दो फ़ंक्शन लिखे, जो नोड को डीकोड करने के बाद, बाइट प्रारूप में लिंक लौटाते हैं, और बचाने से पहले यदि आवश्यक हो, तो उन्हें डीकोड करें। ये कार्य हैं:

 def _prepare_reference_for_encoding(ref): #    ( ,   ) --  . #       :) if 0 < len(ref) < 32: return rlp.decode(ref) return ref def _prepare_reference_for_usage(ref): #     -   . #          . if isinstance(ref, list): return rlp.encode(ref) return ref 

नोड्स क्लास लिखकर नोड्स के साथ समाप्त करें। इसमें केवल 2 विधियाँ होंगी: नोड को डीकोड करें और नोड को एक लिंक में बदल दें।

 class Node: # class Leaf(...) # class Extension(...) # class Branch(...) def decode(encoded_data): data = rlp.decode(encoded_data) # 17  -  Branch . if len(data) == 17: branches = list(map(_prepare_reference_for_usage, data[:16])) node_data = data[16] return Node.Branch(branches, node_data) #    17,   2.   - . #      ,     . path, is_leaf = NibblePath.decode_with_type(data[0]) if is_leaf: return Node.Leaf(path, data[1]) else: ref = _prepare_reference_for_usage(data[1]) return Node.Extension(path, ref) def into_reference(node): #    . #      32 , #   -   . #       . encoded_node = node.encode() if len(encoded_node) < 32: return encoded_node else: return keccak_hash(encoded_node) 

एक विराम

ओह! बहुत सारी जानकारी है। मुझे लगता है कि यह आराम करने का समय है। यहाँ आपके लिए एक और बिल्ली है:

मिलाता है, है ना? ठीक है, हमारे पेड़ों पर वापस।

MerklePatriciaTrie

हुर्रे - सहायक तत्व तैयार हैं, हम सबसे स्वादिष्ट पास करते हैं। बस के मामले में, मैं हमारे पेड़ का इंटरफ़ेस याद दिलाता हूँ। उसी समय, हम __init__ विधि को लागू करते हैं।

 class MerklePatriciaTrie: def __init__(self, storage, root=None): self._storage = storage self._root = root def root(self): pass def get(self, encoded_key): pass def update(self, encoded_key, encoded_value): pass def delete(self, encoded_key): pass 

लेकिन शेष विधियों के साथ हम एक-एक करके निपटेंगे।

प्राप्त

get विधि (जैसे, सिद्धांत रूप में, अन्य विधियां) दो भागों से मिलकर बनेगी। विधि स्वयं डेटा तैयार करेगी और परिणाम को अपेक्षित रूप में लाएगी, जबकि वास्तविक कार्य सहायक विधि के अंदर होगा।

मूल विधि अत्यंत सरल है:

 class MerklePatriciaTrie: # ... def get(self, encoded_key): if not self._root: raise KeyError path = NibblePath(encoded_key) #       #  ,    ,    . result_node = self._get(self._root, path) if type(result_node) is Node.Extension or len(result_node.data) == 0: raise KeyError return result_node.data 

हालांकि, _get अधिक जटिल नहीं है: वांछित नोड को प्राप्त करने के लिए, हमें रूट से पूरे प्रदान किए गए पथ पर जाने की आवश्यकता है। यदि अंत में हमें डेटा (लीफ या ब्रांच) के साथ एक नोड मिला - हुर्रे, डेटा प्राप्त होता है। यदि यह पारित करना संभव नहीं था, तो पेड़ में आवश्यक कुंजी गायब है।

कार्यान्वयन:

 class MerklePatriciaTrie: # ... def _get(self, node_ref, path): #      . node = self._get_node(node_ref) #    --   . #   ,      . if len(path) == 0: return node if type(node) is Node.Leaf: #     Leaf-,     , #      . if node.path == path: return node elif type(node) is Node.Extension: #    -- Extension,    . if path.starts_with(node.path): rest_path = path.consume(len(node.path)) return self._get(node.next_ref, rest_path) elif type(node) is Node.Branch: #    -- Branch,     . #   ,           #  :      . branch = node.branches[path.at(0)] if len(branch) > 0: return self._get(branch, path.consume(1)) #    ,        , #     . raise KeyError 

ठीक है, उसी समय, हम नोड्स को बचाने और लोड करने के तरीके लिखेंगे। वे सरल हैं:

 class MerklePatriciaTrie: # ... def _get_node(self, node_ref): raw_node = None if len(node_ref) == 32: raw_node = self._storage[node_ref] else: raw_node = node_ref return Node.decode(raw_node) def _store_node(self, node): reference = Node.into_reference(node) if len(reference) == 32: self._storage[reference] = node.encode() return reference 

अद्यतन

update विधि पहले से अधिक दिलचस्प है। बस अंत तक जाएं और लीफ नोड डालें हमेशा काम नहीं करेगा। यह संभावना है कि कुंजी पृथक्करण बिंदु पहले से सहेजे गए लीफ या एक्सटेंशन नोड के अंदर कहीं होगा। इस मामले में, आपको उन्हें अलग करना होगा और कई नए नोड्स बनाने होंगे।

सामान्य तौर पर, सभी तर्क निम्नलिखित नियमों द्वारा वर्णित किए जा सकते हैं:

1. जबकि पथ पूरी तरह से मौजूदा नोड्स के साथ मेल खाता है, हम पुनरावर्ती रूप से पेड़ से उतरते हैं।
2. यदि पथ समाप्त हो गया है और हम शाखा या लीफ नोड में हैं, तो इसका मतलब है कि update केवल इस कुंजी के अनुरूप मूल्य को अपडेट करता है।
3. यदि पथ विभाजित हैं (अर्थात, हम मान को अद्यतन नहीं करते हैं, लेकिन एक नया डालें), और हम शाखा नोड में हैं, एक लीफ नोड बनाएँ और संबंधित शाखा शाखा शाखा में एक लिंक निर्दिष्ट करें।
4. यदि पथ विभाजित हैं और हम एक पत्ती या एक्सटेंशन नोड में हैं, तो हमें एक शाखा नोड बनाने की आवश्यकता है जो पथों को अलग करता है, और यदि आवश्यक हो, तो पथ के सामान्य भाग के लिए एक एक्सटेंशन नोड।

धीरे-धीरे इसे कोड में व्यक्त करते हैं। धीरे-धीरे क्यों? क्योंकि विधि बड़ी है और इसे थोक में समझना मुश्किल होगा।
हालांकि, मैं यहां पूरी विधि का लिंक छोड़ दूंगा।

 class MerklePatriciaTrie: # ... def update(self, encoded_key, encoded_value): path = NibblePath(encoded_key) result = self._update(self._root, path, encoded_value) self._root = result def _update(self, node_ref, path, value): #       (,   ), #       . if not node_ref: return self._store_node(Node.Leaf(path, value)) #          #    . node = self._get_node(node_ref) if type(node) == Node.Leaf: ... elif type(node) == Node.Extension: ... elif type(node) == Node.Branch: ... 

पर्याप्त सामान्य तर्क नहीं है, सभी सबसे दिलचस्प if अंदर है।

if type(node) == Node.Leaf

सबसे पहले, लीफ नोड्स से निपटें। केवल 2 परिदृश्य उनके साथ संभव हैं:

1. हम जिस पथ का अनुसरण कर रहे हैं, वह ठीक उसी तरह का है, जैसा कि पत्ती नोड में संग्रहित पथ। इस मामले में, हमें बस मान बदलने की जरूरत है, नए नोड को बचाएं और इसके लिए एक लिंक लौटाएं।

   
   

2. रास्ते अलग हैं।
   इस स्थिति में, आपको एक शाखा नोड बनाने की आवश्यकता है जो दो रास्तों को अलग करता है।
   यदि कोई एक पथ खाली है, तो उसका मान सीधे शाखा-नोड को स्थानांतरित कर दिया जाएगा।
   अन्यथा, हमें रास्तों के आम हिस्से की लंबाई से छोटे दो लीफ नोड्स बनाने होंगे + 1 कुतरना (यह कुतरना शाखा नोड के इसी शाखा के सूचकांक द्वारा इंगित किया जाएगा)।

   
   

आपको यह भी जांचने की आवश्यकता होगी कि क्या यह समझने के लिए कि क्या हमें एक्सटेंशन नोड बनाने की आवश्यकता है, मार्ग का एक सामान्य हिस्सा है या नहीं।

कोड में, यह इस तरह दिखेगा:

 if type(node) == Node.Leaf: if node.path == path: #  .       . node.data = value return self._store_node(node) #    . #    . common_prefix = path.common_prefix(node.path) #      . path.consume(len(common_prefix)) node.path.consume(len(common_prefix)) #  Branch . branch_reference = self._create_branch_node(path, value, node.path, node.data) # ,    Extension-. if len(common_prefix) != 0: return self._store_node(Node.Extension(common_prefix, branch_reference)) else: return branch_reference 

_create_branch_node प्रक्रिया निम्नानुसार है:

 def _create_branch_node(self, path_a, value_a, path_b, value_b): #    Branch-. branches = [b''] * 16 # ,     Branch- . branch_value = b'' if len(path_a) == 0: branch_value = value_a elif len(path_b) == 0: branch_value = value_b #    Leaf-,  . self._create_branch_leaf(path_a, value_a, branches) self._create_branch_leaf(path_b, value_b, branches) #  Branch-     . return self._store_node(Node.Branch(branches, branch_value)) def _create_branch_leaf(self, path, value, branches): # ,     Leaf-. if len(path) > 0: #    ( ). idx = path.at(0) #  Leaf-   ,     . leaf_ref = self._store_node(Node.Leaf(path.consume(1), value)) branches[idx] = leaf_ref 

if type(node) == Node.Extension

एक्सटेंशन नोड के मामले में, सब कुछ एक लीफ नोड की तरह दिखता है।

1. यदि एक्सटेंशन नोड से पथ हमारे पथ के लिए एक उपसर्ग है, तो हम बस पुनरावर्ती रूप से आगे बढ़ते हैं।

   
   

2. अन्यथा, हमें शाखा नोड का उपयोग करके पृथक्करण करने की आवश्यकता है, जैसा कि ऊपर वर्णित मामले में है।

   
   

तदनुसार, कोड:

 elif type(node) == Node.Extension: if path.starts_with(node.path): #         . new_reference = \ self._update(node.next_ref, path.consume(len(node.path)), value) return self._store_node(Node.Extension(node.path, new_reference)) #  Extension-. #     . common_prefix = path.common_prefix(node.path) #  . path.consume(len(common_prefix)) node.path.consume(len(common_prefix)) #  Branch- ,  ,    . branches = [b''] * 16 branch_value = value if len(path) == 0 else b'' #     Leaf-  Extension- . self._create_branch_leaf(path, value, branches) self._create_branch_extension(node.path, node.next_ref, branches) branch_reference = self._store_node(Node.Branch(branches, branch_value)) # ,    Extension-. if len(common_prefix) != 0: return self._store_node(Node.Extension(common_prefix, branch_reference)) else: return branch_reference 

_create_branch_extension प्रक्रिया तार्किक रूप से _create_branch_leaf प्रक्रिया के बराबर है, लेकिन यह एक्सटेंशन नोड के साथ काम करता है।

if type(node) == Node.Branch

लेकिन शाखा-नोड के साथ, सब कुछ सरल है। यदि रास्ता खाली है, तो हम वर्तमान शाखा नोड में नए मान को सहेजते हैं। यदि रास्ता खाली नहीं है, तो हम इसमें से एक कुतरते हैं और फिर से नीचे जाते हैं।

मुझे लगता है कि कोड को टिप्पणियों की आवश्यकता नहीं है।

 elif type(node) == Node.Branch: if len(path) == 0: return self._store_node(Node.Branch(node.branches, value)) idx = path.at(0) new_reference = self._update(node.branches[idx], path.consume(1), value) node.branches[idx] = new_reference return self._store_node(node) 

हटाना

ओह! अंतिम विधि बनी हुई है। वह सबसे हंसमुख है। विलोपन की जटिलता यह है कि हमें उस संरचना को उस स्थिति में वापस करने की आवश्यकता है जिसमें यह गिर गया होगा यदि हमने update की पूरी श्रृंखला को हटा दिया था, केवल हटाए गए कुंजी को छोड़कर।

, , , , . "", , .

. , N- , N+1 . enum — DeleteAction , .

delete :

 class MerklePatriciaTrie: # ... # Enum, ,         . class _DeleteAction(Enum): #    . #     , #        (_DeleteAction, None). DELETED = 1, #    (,    ). #     ,    #    : (_DeleteAction, ___). UPDATED = 2, #    Branch-  .   -- #    : # (_DeleteAction, (___, ___)) USELESS_BRANCH = 3 def delete(self, encoded_key): if self._root is None: return path = NibblePath(encoded_key) action, info = self._delete(self._root, path) if action == MerklePatriciaTrie._DeleteAction.DELETED: #   . self._root = None elif action == MerklePatriciaTrie._DeleteAction.UPDATED: #   . new_root = info self._root = new_root elif action == MerklePatriciaTrie._DeleteAction.USELESS_BRANCH: #   . _, new_root = info self._root = new_root def _delete(self, node_ref, path): node = self._get_node(node_ref) if type(node) == Node.Leaf: pass elif type(node) == Node.Extension: pass elif type(node) == Node.Branch: pass 

, get update . . .

if type(node) == Node.Leaf

. . — , , .

:

 if type(node) == Node.Leaf: if path == node.path: return MerklePatriciaTrie._DeleteAction.DELETED, None else: raise KeyError 

, "" — . , . .

if type(node) == Node.Extension

C Extension- :

1. , Extension- . — .
2. _delete , "" .
3. . :

• . .
• . .
• Branch-. . , Branch- . , , Leaf-. — Extension-.

:

 elif type(node) == Node.Extension: if not path.starts_with(node.path): raise KeyError #   . #       . action, info = self._delete(node.next_ref, path.consume(len(node.path))) if action == MerklePatriciaTrie._DeleteAction.DELETED: return action, None elif action == MerklePatriciaTrie._DeleteAction.UPDATED: #    ,     . child_ref = info new_ref = self._store_node(Node.Extension(node.path, child_ref)) return action, new_ref elif action == MerklePatriciaTrie._DeleteAction.USELESS_BRANCH: #     Branch-. stored_path, stored_ref = info # ,     Branch-. child = self._get_node(stored_ref) new_node = None if type(child) == Node.Leaf: #  branch-  . #     Leaf-  Extension. path = NibblePath.combine(node.path, child.path) new_node = Node.Leaf(path, child.data) elif type(child) == Node.Extension: #  Branch-  Extension-. #       . path = NibblePath.combine(node.path, child.path) new_node = Node.Extension(path, child.next_ref) elif type(child) == Node.Branch: #  Branch-      Branch-. #    Extension-    . path = NibblePath.combine(node.path, stored_path) new_node = Node.Extension(path, stored_ref) new_reference = self._store_node(new_node) return MerklePatriciaTrie._DeleteAction.UPDATED, new_reference 

if type(node) == Node.Branch

.

, . Branch-, …

क्यों? Branch- Leaf- ( ) Extension- ( ).
, . , — Leaf-. — Extension-. , , 2 — Branch- .

? :

:

1. , .
2. , _delete .

:

 elif type(node) == Node.Branch: action = None idx = None info = None if len(path) == 0 and len(node.data) == 0: raise KeyError elif len(path) == 0 and len(node.data) != 0: node.data = b'' action = MerklePatriciaTrie._DeleteAction.DELETED else: #   ,    . #    . idx = path.at(0) if len(node.branches[idx]) == 0: raise KeyError action, info = self._delete(node.branches[idx], path.consume(1)) #  ,   ,  . #      -    #    . node.branches[idx] = b'' 

_DeleteAction .

1. Branch- , ( , ). .

 if action == MerklePatriciaTrie._DeleteAction.UPDATED: #   . next_ref = info node.branches[idx] = next_ref reference = self._store_node(node) return MerklePatriciaTrie._DeleteAction.UPDATED, reference elif action == MerklePatriciaTrie._DeleteAction.USELESS_BRANCH: #    . _, next_ref = info node.branches[idx] = next_ref reference = self._store_node(node) return MerklePatriciaTrie._DeleteAction.UPDATED, reference 

1. ( , ), , .

. :

• . , , , . , .
• , . Leaf- . .
• , . , , .
• , , Branch- . , _DeleteAction — UPDATED .

 if action == MerklePatriciaTrie._DeleteAction.DELETED: non_empty_count = sum(map(lambda x: 1 if len(x) > 0 else 0, node.branches)) if non_empty_count == 0 and len(node.data) == 0: # Branch- ,  . return MerklePatriciaTrie._DeleteAction.DELETED, None elif non_empty_count == 0 and len(node.data) != 0: #  ,   . path = NibblePath([]) reference = self._store_node(Node.Leaf(path, node.data)) return MerklePatriciaTrie._DeleteAction.USELESS_BRANCH, (path, reference) elif non_empty_count == 1 and len(node.data) == 0: #  ,   . return self._build_new_node_from_last_branch(node.branches) else: #  1+   ,  2+ . # Branch-  ,   - UPDATED. reference = self._store_node(node) return MerklePatriciaTrie._DeleteAction.UPDATED, reference 

_build_new_node_from_last_branch .

— Leaf Extension, , .

— Branch, Extension , , Branch.

 def _build_new_node_from_last_branch(self, branches): #    . idx = 0 for i in range(len(branches)): if len(branches[i]) > 0: idx = i break #     . prefix_nibble = NibblePath([idx], offset=1) #     child = self._get_node(branches[idx]) path = None node = None #   . if type(child) == Node.Leaf: path = NibblePath.combine(prefix_nibble, child.path) node = Node.Leaf(path, child.data) elif type(child) == Node.Extension: path = NibblePath.combine(prefix_nibble, child.path) node = Node.Extension(path, child.next_ref) elif type(child) == Node.Branch: path = prefix_nibble node = Node.Extension(path, branches[idx]) #  . reference = self._store_node(node) return MerklePatriciaTrie._DeleteAction.USELESS_BRANCH, (path, reference) 

बाकी

. , … root .

यहां:

 class MerklePatriciaTrie: # ... def root(self): return self._root 

, .

… . , , Ethereum . , , , . , :)

, , pip install -U eth_mpt — .

परिणाम

?

, -, , - , , . — , .

-, , , — . , skip list interval tree, — , , .

-, , . , - .

-, — .

, , — !

: 1 , 2 , 3 . ! , .