आरडीबीएमएस में एक आदेशित सूची के लिए सबसे उपयुक्त डेटा संरचना?

Question

मैं एक MySQL डेटाबेस में कई मिलियन आइटमों की ऑर्डर की गई सूची संग्रहीत कर रहा हूं। उचित रूप से, वस्तुओं को सूची से जोड़ा या हटा दिया जाना चाहिए; समान रूप से, किसी आइटम की सूची में स्थिति निर्धारित की जानी चाहिए। मैं कहूंगा कि पढ़ना/लिखना अनुपात लगभग 50:50 है।

एक लिंक किए गए सूची मॉडल से शुरू, मैंने [1] और वहां चर्चा की गई विभिन्न मॉडलों को पढ़ा। सख्त लिंक्ड-लिस्ट के लिए, आसन्नता सूची मॉडल ठीक काम करेगा, लेकिन चूंकि पढ़ने/लिखने का अनुपात कम या कम बराबर होता है, इसलिए मैं मानक संगत सूचियों का उपयोग करके विभाजन को विभाजित करता हूं और दृष्टिकोण प्राप्त करता हूं:

संपूर्ण सूची को विभाजित करें अनुमानित लंबाई की 'बाल्टी' (~ 10000 कहें) में, मुख्य सूची में बाल्टी आकार और उनकी सापेक्ष स्थिति की एक सूचकांक बनाए रखना। प्रत्येक आइटम को एक विशिष्ट बाल्टी को सौंपा जाता है और उस बाल्टी के भीतर अपनी स्थिति का ट्रैक रखता है।

इस दृष्टिकोण के साथ, किसी आइटम की स्थिति सूची में आइटम की बाल्टी को आगे बढ़ाने वाली बाल्टी के आकार को जोड़कर निर्धारित की जाती है, फिर आइटम की स्थिति को अपनी बाल्टी में जोड़ती है। सूची से किसी आइटम को सम्मिलित/निकालने के लिए, परिणामों का 'स्थानांतरण' जो बाल्टी को स्थानांतरित किया जाता है जिसमें एक आइटम जोड़ा या हटाया जाता है; उस बाल्टी का आकार भी तदनुसार अपडेट किया जाना चाहिए।

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

क्या इस तरह के डेटा को आरडीबीएमएस में रखने के लिए कोई और अनुमोदित दृष्टिकोण हैं? थ्रेड-सुरक्षा समस्या मुझे एक बड़ा सिरदर्द पैदा कर रही है और ऐसा लगता है कि संग्रहीत प्रक्रियाओं का उपयोग करने के लिए मुझे मजबूर करने से इस समस्या को हल करने का एक बेहतर तरीका होना चाहिए।

बहुत धन्यवाद, मैट।

[1] Database Structure for Tree Data Structure

Answer 1

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

• Sorting lists

, इस सरल प्रश्न के साथ:

SELECT @r AS _parent, 
     @r := (
     SELECT id 
     FROM t_list 
     WHERE parent = _parent 
     ) AS id 
FROM (
     SELECT @r := 0 
     ) vars, 
     t_list 

सुनिश्चित करें कि आपके id और parent में UNIQUE इंडेक्स को कुशल होने के लिए परिभाषित किया गया है।

किसी भी id से ब्राउज़ करना प्रारंभ करने के लिए के साथ @r := 0 बदलें।

आइटम की स्थिति को जानने के लिए, बस क्वेरी रिवर्स:

SELECT COUNT(*) 
FROM (
     SELECT @r AS _id, 
       @r := (
       SELECT parent 
       FROM t_list 
       WHERE id = _id 
       ) AS id 
     FROM (
       SELECT @r := @item_id 
       ) vars, 
       t_list 
     ) q