14. البحث في الذاكرة الخارجية
طوال هذا الكتاب، كنّا نستخدم نموذج word-RAM للحساب ذو الكلمة ذات بت المعرَّف في القسم 1.4. ويفترض هذا النموذج ضمنًا أن حاسوبنا يملك ذاكرة وصول عشوائي (random access memory) كبيرة بما يكفي لتخزين كامل بيانات بنية البيانات. وفي بعض المواقف لا يكون هذا الافتراض صحيحًا؛ إذ توجد مجموعات بيانات ضخمة بحيث لا يملك أي حاسوب ذاكرة كافية لتخزينها. وفي هذه الحالات يلجأ التطبيق إلى تخزين البيانات على وسيط تخزين خارجي (external storage) من نوع القرص الصلب (hard disk) أو القرص الحالة (solid state disk) أو حتى خادم ملفات شبكي (network file server) يملك بدوره تخزينًا خارجيًا. والوصول إلى عنصر في التخزين الخارجي بالغ البطء. فالقرص الصلب الموصول بالحاسوب الذي كُتب هذا الكتاب عليه له زمن وصول متوسط قدره 19ms، وقرص الحالة الموصول بالحاسوب له زمن وصول متوسط قدره 0.3ms. وفي المقابل، لذاكرة الوصول العشوائي في الحاسوب زمن وصول متوسط أقل من 0.000113ms. فالوصول إلى RAM أسرع بأكثر من 2500 مرة من الوصول إلى قرص الحالة، وأسرع بأكثر من 160000 مرة من الوصول إلى القرص الصلب. وهذه السرعات نموذجية إلى حدٍّ كبير؛ فقراءة بايت عشوائي من RAM أسرع بآلاف المرات من قراءة بايت عشوائي من قرص صلب أو قرص حالة. غير أن زمن الوصول وحده لا يروي القصة كاملة. فحين نقرأ بايتًا من قرص صلب أو قرص حالة، تُقرأ في الواقع كتلة كاملة من القرص. ولكل قرص موصول بالحاسوب حجم كتلة قدره 4096؛ فكلما قرأنا بايتًا واحدًا، يعطينا القرص كتلة تحتوي 4096 بايت. وإذا نظّمنا بنية بياناتنا بعناية، فإن هذا يعني أن كل وصول إلى القرص يمكن أن يمنحنا 4096 بايت تفيد في إتمام العملية التي ننفّذها. وهذه هي الفكرة الكامنة وراء نموذج الذاكرة الخارجية للحساب، والمبيَّنة تخطيطيًّا في الشكل 14.1. وفي هذا النموذج، يملك الحاسوب وصولًا إلى ذاكرة خارجية كبيرة تقع فيها كل البيانات. وتُقسَّم هذه الذاكرة إلى كتل ذاكرة، كل منها يحتوي كلمة. ويملك الحاسوب كذلك ذاكرة داخلية محدودة يستطيع أن ينفّذ عليها الحسابات. ويستغرق نقل كتلة بين الذاكرة الداخلية والذاكرة الخارجية زمنًا ثابتًا. أما الحسابات المنفَّذة داخل الذاكرة الداخلية فمجانية؛ فهي لا تستغرق أي زمن على الإطلاق. وقد يبدو أن كون عمليات الذاكرة الداخلية مجانية غريبًا بعض الشيء، لكنه لا يبرز سوى المسألة البديهية التي مفادها أن الذاكرة الخارجية أبطأ بكثير من RAM. الشكل 14.1: في نموذج الذاكرة الخارجية، فإن الوصول إلى عنصر مفرد، ، في الذاكرة الخارجية يستلزم قراءة الكتلة كاملة التي تحتوي إلى RAM. وفي نموذج الذاكرة الخارجية الكامل، يكون حجم الذاكرة الداخلية معاملًا أيضًا. لكن بالنسبة إلى بنى البيانات الموصوفة في هذا الفصل، تكفي ذاكرة داخلية بحجم . أي أن الذاكرة يلزم أن قادرة على تخزين عدد ثابت من الكتل ومكدس تعاود (recursion stack) بارتفاع . وفي معظم الحالات، يهيمن الحدّ على متطلّب الذاكرة. فمثلًا، حتى مع القيمة الصغيرة نسبيًا ، فإن لكل . وبالتدوين العشري، فإن لأي
الأقسام الفرعية
14.1 مخزن الكتل
يشمل مفهوم الذاكرة الخارجية عددًا كبيرًا من الأجهزة المختلفة المحتملة، لكلٍّ منها حجم كتلته الخاص ويُوصَل إليها بمجموعة استدعاءات النظام (system calls) الخاصة به. ولتبسيط عرض هذا الفصل حتى نركّز على الأفكار المشتركة، نغلّف أجهزة الذاكرة الخارجية بكائن يُسمّى BlockStore. ويخزّن BlockStore مجموعة من كتل الذاكرة، كل منها بحجم . وتُعرَّف كل كتلة بصورة فريدة بفهرسها الصحيح. ويدعم BlockStore العمليات التالية:
- : أعِد محتويات الكتلة التي فهرسها .
- : اكتب محتويات في الكتلة التي فهرسها .
- : أعِد فهرسًا جديدًا وخزّن محتويات عند هذا الفهرس.
- : حرِّر الكتلة التي فهرسها . وهذا يعني أن محتويات هذه الكتلة لم تعد مستخدَمة، ولذلك يمكن إعادة استعمال الذاكرة الخارجية المخصَّصة لها.
أسهل طريقة لتخيّل BlockStore هي أن نتخيّله وكأنه يخزّن ملفًا على القرص مُقسَّمًا إلى كتل، كل منها يحتوي بايت. وبهذه الطريقة، لا يفعل و سوى قراءة البايتات وكتابتها في هذا الملف. وإلى جانب ذلك، قد يحتفظ BlockStore بسيط بقائمة كتل حرّة (free list) من الكتل المتاحة للاستعمال. وتُضاف الكتل المُحرَّرة بواسطة إلى قائمة الكتل الحرّة. وبهذه الطريقة، يستطيع أن يستعمل كتلة من قائمة الكتل الحرّة، أو، إن لم تكن هناك كتلة متاحة، أن يُلحق كتلة جديدة بنهاية الملف. opendatastructures.org
14.2 أشجار B
الأقسام الفرعية
14.2 أشجار B
في هذا القسم نناقش تعميمًا للأشجار الثنائية، تُسمّى أشجار (B-trees)، وهو كفؤ في نموذج الذاكرة الخارجية. وبدلًا من ذلك، يمكن النظر إلى أشجار على أنها التعميم الطبيعي لأشجار 2-4 الموصوفة في القسم 9.1. (وشجرة 2-4 هي حالة خاصة من شجرة نحصل عليها بضبط .) ولأي عدد صحيح ، شجرة هي شجرة تتساوى فيها أعماق كل الأوراق، ولكل عقدة داخلية غير جذرية، ، عدد أبناء لا يقل عن ولا يزيد عن . وتُخزَّن أبناء في مصفوفة، . أمّا الشرط على عدد الأبناء فيُخفَّف عند الجذر، الذي يمكن أن يملك ما بين 2 و ابنًا. فإذا كان ارتفاع شجرة هو ، فإن ذلك يعني أن عدد الأوراق، ، في شجرة يحقّق
بأخذ لوغاريتم المتباينة الأولى وإعادة ترتيب الحدود نحصل على:
بمعنى آخر، إن ارتفاع شجرة متناسب مع لوغاريتم عدد الأوراق بالأساس .
تخزّن كل عقدة، ، في شجرة مصفوفة مفاتيح . فإذا كانت عقدة داخلية لها ابنًا، فإن عدد المفاتيح المخزَّنة في هو بالضبط، وتُخزَّن في . أمّا مداخل مصفوفة الباقية وعددها فتُضبط على . وإذا كانت عقدة ورقة غير جذرية، فإن تحتوي ما بين و مفتاحًا. وتخضع مفاتيح شجرة لترتيب مشابه لترتيب مفاتيح شجرة البحث الثنائية. فلكل عقدة، ، تخزّن مفاتيح،
فإذا كانت عقدة داخلية، فإن لكل يكون أكبر من كل مفتاح مخزَّن في الشجرة الفرعية المجذّرة عند وأصغر من كل مفتاح مخزَّن في الشجرة الفرعية المجذّرة عند . وبعبارة غير رسمية،
يبيّن الشكل 14.2 مثالًا لشجرة مع .
الشكل 14.2: شجرة مع . 
لاحظ أن البيانات المخزَّنة في عقدة شجرة حجمها . ولذلك، في سياق الذاكرة الخارجية، تُختار قيمة في شجرة بحيث تتّسع العقدة في كتلة ذاكرة خارجية واحدة. وبهذه الطريقة، يكون الزمن اللازم لتنفيذ عملية على شجرة في نموذج الذاكرة الخارجية متناسبًا مع عدد العقد التي تصل إليها العملية (تقرأها أو تكتبها). فمثلًا، إذا كانت المفاتيح أعدادًا صحيحة ذات 4 بايتات وكانت فهارس العقد كذلك بحجم 4 بايتات، فإن ضبط يعني أن كل عقدة تخزّن
بايتًا من البيانات. وستكون هذه قيمة مثالية لـ في حالة القرص الصلب أو قرص الحالة المذكورين في مقدمة هذا الفصل، إذ إن حجم الكتلة عندهما بايت. أمّا الصنف BTree، الذي ينفّذ شجرة ، فيخزّن BlockStore هو ، يخزّن عقد BTree، وكذلك فهرس عقدة الجذر، . وكالمعتاد، يُستخدَم عدد صحيح، ، لتتبّع عدد العناصر في بنية البيانات:
int n;
BlockStore<Node> bs;
int ri;
14.2.1 البحث
يعمّم تنفيذ عملية ، والمبيَّن في الشكل 14.3، عملية في شجرة البحث الثنائية. يبدأ البحث عن من الجذر، ويستخدم المفاتيح المخزَّنة في عقدة، ، لتحديد أي من أبناء ينبغي أن يتواصل البحث عنده.
وبتحديد أكثر، عند عقدة ، يفحص البحث ما إذا كانت مخزَّنة في . فإن كان الأمر كذلك، فقد وُجدت واكتمل البحث. وإلا فإن البحث يجد أصغر عدد صحيح، ، بحيث ويواصل البحث في الشجرة الفرعية المجذّرة عند . فإذا لم يكن في أي مفتاح أكبر من ، فإن البحث يتواصل في الابن الأيمن لـ . وكما في أشجار البحث الثنائية بالضبط، يتتبّع الخوارزم آخر مفتاح رآه، ، ويكون أكبر من . وحالَما لا تُوجد ، يُعاد بوصفه أصغر قيمة أكبر من أو تساويها.
T find(T x) {
T z = null;
int ui = ri;
while (ui >= 0) {
Node u = bs.readBlock(ui);
int i = findIt(u.keys, x);
if (i < 0) return u.keys[-(i+1)]; // found it
if (u.keys[i] != null)
z = u.keys[i];
ui = u.children[i];
}
return z;
}
جوهر طريقة هو طريقة التي تبحث في مصفوفة مرتَّبة معبَّأة بـ ، ، عن القيمة . وتعمل هذه الطريقة، والمبيَّنة في الشكل 14.4، مع أي مصفوفة، ، يكون فيها تسلسلًا من المفاتيح مرتَّبًا، وتكون فيها كلّها مضبوطة على . فإذا كانت في المصفوفة عند الموضع ، فإن تُعيد . وإلا فإنها تُعيد أصغر فهرس، ، بحيث أو .
int findIt(T[] a, T x) {
int lo = 0, hi = a.length;
while (hi != lo) {
int m = (hi+lo)/2;
int cmp = a[m] == null ? -1 : compare(x, a[m]);
if (cmp < 0)
hi = m; // look in first half
else if (cmp > 0)
lo = m+1; // look in second half
else
return -m-1; // found it
}
return lo;
}
تستخدم طريقة بحثًا ثنائيًا (binary search) يُنصّف فضاء البحث عند كل خطوة، ولذلك تعمل في زمن . وفي حالتنا، ، ولذلك تعمل في زمن .
يمكننا تحليل زمن تنفيذ عملية على شجرة في نموذج word-RAM المعتاد (حيث تُحسب كل تعليمة) وفي نموذج الذاكرة الخارجية (حيث نعدّ عدد العقد التي نصل إليها فحسب). ولأن كل ورقة في شجرة تخزّن مفتاحًا واحدًا على الأقل، وأن ارتفاع شجرة ذات ورقة هو ، فإن ارتفاع شجرة تخزّن مفتاحًا هو . ولذلك، في نموذج الذاكرة الخارجية، الزمن الذي تستغرقه عملية هو . أما لتحديد زمن التنفيذ في نموذج word-RAM فيتعين علينا احتساب كلفة استدعاء عند كل عقدة نصل إليها، ومن ثمّ فإن زمن تنفيذ في نموذج word-RAM هو
14.2.2 الإضافة
هناك فرق مهم بين أشجار وبنية بيانات BinarySearchTree المذكورة في القسم 6.2، وهو أن عقد شجرة لا تخزّن مؤشرات إلى آباءها. وسيُشرح سبب ذلك بعد قليل. وغياب مؤشرات الأمّ يعني أن عمليتي و على أشجار يُعتمَل بهما على نحو أسهل ما يكون بالتعاود (recursion). وكما في كل أشجار البحث المتوازنة، يلزم شكلٌ من إعادة التوازن أثناء عملية . وفي شجرة يتم ذلك بتقسيم العقد. انظر الشكل 14.5 لما يأتي. ومع أن التقسيم يجري عبر مستويين من التعاود، فمن الأفضل فهمه كعملية تأخذ عقدة، ، تحتوي مفتاحًا ولها ابنًا. فهي تنشئ عقدة جديدة، ، تتبنّى . وتتبنّى العقدة الجديدة أيضًا أكبر مفاتيح لـ ، أي . وعند هذه النقطة، تكون ذات أبناء و مفاتيح. أمّا المفتاح الزائد، ، فيُمرَّر إلى أمّ التي تتبنّى هي الأخرى . ولاحظ أن عملية التقسيم تعدّل ثلاث عقد: ، وأمّ ، والعقدة الجديدة . ولهذا فمن المهم ألّا تحتفظ عقد شجرة بمؤشرات الأمّ. فإذا كانت تفعل ذلك، لكان على الأبناء الـ التي تتبنّاها أن تُعدَّل مؤشرات أمّاتها جميعًا. وهذا يزيد عدد عمليات الوصول إلى الذاكرة الخارجية من 3 إلى ويجعل أشجار أقل كفاءة بكثير مع قيم الكبيرة.
 |
||
|---|---|---|
 |
يبيّن الشكل 14.6 طريقة في شجرة . وعلى مستوى عالٍ، تجد هذه الطريقة ورقة، ، تُضاف عندها القيمة . فإذا أدّى هذا إلى أن تتجاوز طاقتها (لأنها كانت تحتوي أصلًا على مفاتيح)، فإن تُقسَّم. فإذا أدّى هذا إلى أن تتجاوز أمّ طاقتها، فإن أمّ تُقسَّم هي الأخرى، وقد يسبّب ذلك تجاوز جدّة لطاقتها، وهكذا. ويستمر هذا المسار، صاعدًا في الشجرة مستوى بعد مستوى، حتى يبلغ عقدة لا تتجاوز طاقتها أو حتى يُقسَّم الجذر. وفي الحالة الأولى تتوقف العملية. وفي الحالة الثانية يُنشأ جذر جديد يصير ابناه هما العقدتان الناتجتان عند تقسيم الجذر الأصلي.
 |
||
|---|---|---|
 |
||
 |
الملخّص التنفيذي لطريقة هو أنها تنطلق من الجذر إلى ورقة بحثًا عن ، وتضيف إلى هذه الورقة، ثم تعود صاعدةً إلى الجذر، مقسِّمةً أي عقدة تتجاوز طاقتها تصادفها في الطريق. ومع هذه الرؤية العامة في الأذهان، يمكننا الآن التعمّق في تفاصيل كيفية تنفيذ هذه الطريقة تعاوديًا. فالعمل الحقيقي لطريقة تقوم به طريقة التي تضيف القيمة إلى الشجرة الفرعية التي جذرها، ، له المعرِّف . فإذا كانت ورقة، فإن تُدرَج ببساطة في . وإلا فإن تُضاف تعاوديًا إلى الابن المناسب، ، لـ . ونتيجة هذا الاستدعاء التعاودي تكون عادةً ، لكنها قد تكون أيضًا مرجعًا إلى عقدة أُنشئت حديثًا، ، وقد أُنشئت لأن قُسِّمت. وفي هذه الحالة تتبنّى العقدة وتؤخذ مفتاحها الأول، مما يُكمل عملية التقسيم على . وبعد أن تُضاف القيمة (سواء إلى أو إلى نسل من )، تفحص طريقة ما إذا كانت تخزّن عددًا كبيرًا من المفاتيح (أكثر من ). فإذا كان الأمر كذلك، فيلزم تقسيم باستدعاء طريقة . ونتيجة استدعاء هي عقدة جديدة تُستخدَم بوصفها القيمة المُعادة لطريقة .
Node addRecursive(T x, int ui) throws DuplicateValueException {
Node u = bs.readBlock(ui);
int i = findIt(u.keys, x);
if (i < 0) throw new DuplicateValueException();
if (u.children[i] < 0) { // leaf node, just add it
u.add(x, -1);
bs.writeBlock(u.id, u);
} else {
Node w = addRecursive(x, u.children[i]);
if (w != null) { // child was split, w is new child
x = w.remove(0);
bs.writeBlock(w.id, w);
u.add(x, w.id);
bs.writeBlock(u.id, u);
}
}
return u.isFull() ? u.split() : null;
}
طريقة هي دالة مساعدة لطريقة ، وهي تستدعي لإدراج في جذر شجرة . فإذا أدّى إلى تقسيم الجذر، فإن جذرًا جديدًا يُنشأ ويتبنّى ابنيه الجذر القديم والعقدة الجديدة الناتجة عن تقسيمه.
boolean add(T x) {
Node w;
try {
w = addRecursive(x, ri);
} catch (DuplicateValueException e) {
return false;
}
if (w != null) { // root was split, make new root
Node newroot = new Node();
x = w.remove(0);
bs.writeBlock(w.id, w);
newroot.children[0] = ri;
newroot.keys[0] = x;
newroot.children[1] = w.id;
ri = newroot.id;
bs.writeBlock(ri, newroot);
}
n++;
return true;
}
يمكن تحليل طريقة ودالتها المساعدة، ، في مرحلتين: المرحلة الهابطة: أثناء المرحلة الهابطة من التعاود، وقبل أن تُضاف ، تصلان إلى تسلسل من عقد BTree وتستدعيان عند كل عقدة. وكما في طريقة ، يستغرق هذا زمنًا قدره في نموذج الذاكرة الخارجية وزمنًا قدره في نموذج word-RAM. المرحلة الصاعدة: أثناء المرحلة الصاعدة من التعاود، وبعد أن تُضاف ، تؤدّيان هاتان الدالتان تسلسلًا من عمليات التقسيم وعددها على الأكثر . ولكل عملية تقسيم ثلاث عقد فقط، ولذلك تستغرق هذه المرحلة زمنًا قدره في نموذج الذاكرة الخارجية. غير أن كل عملية تقسيم تنطوي على نقل مفتاحًا وابنًا من عقدة إلى أخرى، ولذلك فإنها في نموذج word-RAM تستغرق زمنًا قدره . وتذكّر أن قيمة قد تكون كبيرة جدًّا، أكبر بكثير حتى من . ولذلك، في نموذج word-RAM، قد تكون إضافة قيمة إلى شجرة أبطأ بكثير من الإضافة إلى شجرة بحث ثنائية متوازنة. وسنبيّن لاحقًا، في القسم 14.2.4، أن الوضع ليس سيئًا إلى هذا الحدّ؛ إذ إن العدد المُطفأ (amortized) لعمليات التقسيم التي تجري أثناء عملية ثابت. وهذا يُظهر أن زمن تنفيذ عملية (المُطفأ) في نموذج word-RAM هو .
14.2.3 الحذف
عملية في BTree، هي أيضًا، أسهل ما تكون تنفيذًا بطريقة تعاودية. ومع أن التنفيذ التعاودي لطريقة يوزّع التعقيد على عدة دوال، فإن العملية الكلية، والمبيَّنة في الشكل 14.7، مباشرة إلى حدٍّ كبير. فبتبديل المفاتيح موضعًا، يُختزل الحذف في مسألة حذف قيمة، ، من ورقة ما، . وقد يترك حذف في أقل من مفتاحًا؛ وتُسمّى هذه الحالة بالنقص (underflow).
 |
||
|---|---|---|
 |
||
 |
||
 |
عند حدوث نقص، فإن تستعير مفاتيح من أحد أشقائها (siblings) أو تُدمج معه. فإذا دُمجت مع شقيق، صارت لأمّ الآن ابنة أقل ومفتاح أقل، وقد يسبّب ذلك نقصًا عند أمّ ؛ ويُصحَّح هذا بدوره بالاستعارة أو بالدمج، لكن الدمج قد يسبّب نقصًا عند جدّة . ويعمل هذا المسار عائدًا إلى الجذر حتى لا يعود هناك نقص، أو حتى يُدمج آخر ابنتين للجذر في ابنة واحدة. وحين تقع الحالة الأخيرة، يُحذف الجذر وتصير ابنته الوحيدة جذرًا جديدًا. بعد ذلك نتعمّق في تفاصيل كيفية تنفيذ كل واحدة من هذه الخطوات. فأول مهمة لطريقة هي إيجاد العنصر الذي ينبغي حذفه. فإذا وُجدت في ورقة، فإن تُحذف من تلك الورقة. وإلا، إذا وُجدت عند في عقدة داخلية ما، ، فإن الخوارزم يحذف أصغر قيمة، ، في الشجرة الفرعية المجذّرة عند . وقيمة هي أصغر قيمة مخزَّنة في BTree أكبر من . ثم تُستخدَم قيمة لاستبدال في . ويبيّن الشكل 14.8 هذه العملية.
 |
||
|---|---|---|
 |
طريقة هي تنفيذ تعاودي للخوارزم السابق:
boolean removeRecursive(T x, int ui) {
if (ui < 0) return false; // didn't find it
Node u = bs.readBlock(ui);
int i = findIt(u.keys, x);
if (i < 0) { // found it
i = -(i+1);
if (u.isLeaf()) {
u.remove(i);
} else {
u.keys[i] = removeSmallest(u.children[i+1]);
checkUnderflow(u, i+1);
}
return true;
} else if (removeRecursive(x, u.children[i])) {
checkUnderflow(u, i);
return true;
}
return false;
}
T removeSmallest(int ui) {
Node u = bs.readBlock(ui);
if (u.isLeaf())
return u.remove(0);
T y = removeSmallest(u.children[0]);
checkUnderflow(u, 0);
return y;
}
لاحظ أن تحتاج، بعد أن تحذف تعاوديًا القيمة من الابن رقم لـ ، إلى ضمان أن يظل هذا الابن يملك مفاتيح على الأقل. وفي الشيفرة السابقة يتم ذلك باستعمال دالة اسمها ، تفحص نقصًا في الابن رقم لـ وتصحّحه. ليكن هو الابن رقم لـ . فإذا كان يملك مفتاحًا فقط، فيلزم معالجة ذلك. ويتطلب هذا العلاج استعمال شقيق لـ . وهذا إمّا الابن رقم لـ أو الابن رقم لـ . وسنستعمل عادةً الابن رقم لـ ، وهو الشقيق لـ الواقع مباشرةً إلى يساره. والوقت الوحيد الذي لا ينفع فيه ذلك هو حين ، وعندئذ نستعمل الشقيق الواقع مباشرةً إلى يمين .
void checkUnderflow(Node u, int i) {
if (u.children[i] < 0) return;
if (i == 0)
checkUnderflowZero(u, i); // use u's right sibling
else
checkUnderflowNonZero(u,i);
}
في ما يلي، نركّز على الحالة بحيث يُصحَّح أي نقص عند الابن رقم لـ بمساعدة الابن رقم لـ . أما الحالة فمتشابهة، ويمكن العثور على تفاصيلها في الشيفرة المصدرية المرافقة.
لعلاج نقص عند العقدة ، نحتاج إلى مفاتيح إضافية (وربما أبناء أيضًا) لـ . وهناك طريقتان لفعل ذلك: الاستعارة: إذا كان للعقدة شقيق، ، يملك أكثر من مفتاحًا، فيمكن لـ أن تستعير بعض المفاتيح (وربما أبناء أيضًا) من . وبتحديد أكثر، إذا كان يخزّن مفتاحًا، فإن و معًا يملكان ما مجموعه
مفتاحًا. ومن ثمّ يمكننا نقل مفاتيح من إلى بحيث يمتلك كلٌّ من و ما لا يقل عن مفتاحًا. ويبيّن الشكل 14.9 هذه العملية.
 |
||
|---|---|---|
 |
الدمج: إذا كان يملك مفتاحًا فقط، فعلينا أن نفعل شيئًا أكثر حدّة، إذ لا يستطيع أن يتخلّى عن أي مفتاح لصالح . ولذلك ندمج و كما يبيّن الشكل 14.10. وعملية الدمج هي عكس عملية التقسيم. فهي تأخذ عقدتين تحتويان معًا ما مجموعه مفتاحًا وتدمجهما في عقدة واحدة تحتوي مفتاحًا. (ويأتي المفتاح الإضافي من أنه، حين ندمج و ، تصير لأمّهما المشتركة، ، ذات ابنة أقل، ومن ثمّ عليها أن تفرّط بواحد من مفاتيحها.)
 |
||
|---|---|---|
 |
void checkUnderflowNonZero(Node u, int i) {
Node w = bs.readBlock(u.children[i]); // w is child of u
if (w.size() < B-1) { // underflow at w
Node v = bs.readBlock(u.children[i-1]); // v left of w
if (v.size() > B) { // w can borrow from v
shiftLR(u, i-1, v, w);
} else { // v will absorb w
merge(u, i-1, v, w);
}
}
}
void checkUnderflowZero(Node u, int i) {
Node w = bs.readBlock(u.children[i]); // w is child of u
if (w.size() < B-1) { // underflow at w
Node v = bs.readBlock(u.children[i+1]); // v right of w
if (v.size() > B) { // w can borrow from v
shiftRL(u, i, v, w);
} else { // w will absorb w
merge(u, i, w, v);
u.children[i] = w.id;
}
}
}
باختصار، تتبع طريقة في شجرة مسارًا من الجذر إلى ورقة، وتحذف مفتاحًا من ورقة، ، ثم تنفّذ صفرًا أو أكثر من عمليات الدمج التي تشمل وأسلافها، وتنفّذ عملية استعارة واحدة على الأكثر. ولأن كل عملية دمج أو استعارة تنطوي على تعديل ثلاث عقد فقط، ولا يحدث منها سوى ، تستغرق العملية كلها زمنًا قدره في نموذج الذاكرة الخارجية. غير أن كل عملية دمج أو استعارة تستغرق زمنًا في نموذج word-RAM، ولذلك (على نحو مبدئي) أقصى ما يمكننا قوله عن زمن التنفيذ الذي تتطلبه في نموذج word-RAM هو أنه . 14.2.4 التحليل المُطفأ لأشجار حتى الآن بيّنا أنّه في نموذج الذاكرة الخارجية، زمن تنفيذ و و في شجرة هو . وفي نموذج word-RAM، زمن تنفيذ هو وزمن تنفيذ و هو . وتبيّن المتراجمة التالية أننا، حتى الآن، قد مبالغنا في تقدير عدد عمليات الدمج والتقسيم التي تنفّذها أشجار . المتراجمة 14.1 إن البدء بشجرة فارغة وتنفيذ أي تسلسل من من عمليات و ينتج عن ذلك تنفيذ على الأكثر من عمليات التقسيم والدمج والاستعارة.
إثبات. لقد رُسم ملمّح لهذا الإثبات من قبل في القسم 9.3 في الحالة الخاصة التي يكون فيها . ويمكن إثبات المتراجمة باستعمال مخطّط أرصدة (credit scheme)، يتم فيه ما يلي:
- تُدفع كلفة كل عملية تقسيم أو دمج أو استعارة بأرصدة (credit) اثنين، أي أن رصيدًا يُحذف في كل مرة تحدث فيها إحدى هذه العمليات؛ و
- لا يُنشأ أكثر من ثلاثة أرصدة أثناء أي عملية أو .
ولأن ما يُنشأ من أرصدة لا يتجاوز أبدًا رصيدًا، وأن كل تقسيم ودمج واستعارة يُدفع بأرصدة اثنين، فإن ذلك يعني أن عمليات التقسيم والدمج والاستعارة المنفَّذة لا تتجاوز . وتُصوَّر هذه الأرصدة باستعمال الرمز في الأشكال 14.5 و14.9 و14.10.
ولكي يتتبّع الإثبات هذه الأرصدة، فإنه يحافظ على الثابت التالي للأرصدة: فكل عقدة غير جذرية ذات مفاتيح تخزّن رصيدًا واحدًا، وكل عقدة ذات مفتاحًا تخزّن ثلاثة أرصدة. أمّا العقدة التي تخزّن ما لا يقل عن مفاتيح وعلى الأكثر مفتاحًا فلا يلزم أن تخزّن أي أرصدة. ويبقى أن نبيّن أننا نستطيع الحفاظ على ثابت الأرصدة وتلبية الخاصيتين 1 و2 أعلاه أثناء كل عملية و .
14.2.4.0.1 الإضافة:
لا تنفّذ طريقة أي عمليات دمج أو استعارة، ولذلك لا نحتاج إلا إلى النظر في عمليات التقسيم التي تحدث نتيجة لاستدعاءات .
تحدث كل عملية تقسيم لأن مفتاحًا يُضاف إلى عقدة، ، تحتوي أصلًا على مفتاحًا. وحين يحدث هذا، تُقسَّم إلى عقدتين، و ، لهما و مفتاحًا على التوالي. وقبل هذه العملية كانت تخزّن مفتاحًا، وبالتالي كانت تخزّن ثلاثة أرصدة. ويمكن استخدام رصيدين من هذه الأرصدة لدفع كلفة التقسيم، ويمكن إعطاء الرصيد الثالث إلى (وهي ذات مفاتيح) للحفاظ على ثابت الأرصدة. ولذلك يمكننا دفع كلفة التقسيم والحفاظ على ثابت الأرصدة في أي عملية تقسيم. وأمّا التعديل الوحيد الآخر على العقد الذي يحدث أثناء عملية فيحدث بعد اكتمال كل عمليات التقسيم، إن وُجدت. وينطوي هذا التعديل على إضافة مفتاح جديد إلى بعض العقدة . فإذا كانت ، قبل ذلك، ذات ابنة، فإنها صارت الآن ذات ابنة، ولذلك يجب أن تتلقى ثلاثة أرصدة. وهذه هي الأرصدة الوحيدة التي تمنحها طريقة . 14.2.4.0.2 الحذف: أثناء استدعاء ، تحدث صفر أو أكثر من عمليات الدمج، يليها استعارة واحدة على الأرجح. وتحدث كل عملية دمج لأن عقدتين، و ، كانتا تملكان كلٌّ منهما مفتاحًا بالضبط قبل استدعاء ، دُمجتا في عقدة واحدة ذات مفتاحًا بالضبط. ولذلك تُحرِّر كل عملية دمج كهذه رصيدين يمكن استخدامهما لدفع كلفة الدمج. وبعد تنفيذ أي عمليات دمج، تحدث عملية استعارة واحدة على الأكثر، وبعدها لا تحدث أي عمليات دمج أو استعارة أخرى. ولا تحدث عملية الاستعارة هذه إلا إذا حذفنا مفتاحًا من ورقة، ، ذات مفاتيح. ولذلك تملك العقدة رصيدًا واحدًا، وهذا الرصيد يسهم في كلفة الاستعارة. وهذا الرصيد الواحد لا يكفي لدفع كلفة الاستعارة، فننشئ رصيدًا واحدًا لإتمام السداد. وعند هذه النقطة يكون قد أُنشئ رصيد واحد، ولا يزال علينا أن نبيّن أن ثابت الأرصدة يمكن الحفاظ عليه. وفي أسوأ الحالات، يملك شقيق ، وهو ، مفاتيح بالضبط قبل الاستعارة، بحيث يصير بعد ذلك كلٌّ من و ذا مفاتيح. وهذا يعني أن و ينبغي أن يخزّن كلٌّ منهما رصيدًا عند اكتمال العملية. ولذلك، في هذه الحالة، ننشئ رصيدين إضافيين نمنحهما لـ و . وبما أن الاستعارة تحدث مرة واحدة على الأكثر أثناء عملية ، فإن هذا يعني أننا ننشئ ثلاثة أرصدة على الأكثر، كما هو مطلوب. وإذا لم تتضمن عملية عملية استعارة، فإن ذلك راجع إلى أنها تنتهي بحذف مفتاح من عقدة كانت، قبل العملية، تملك مفاتيح أو أكثر. وفي أسوأ الحالات كانت هذه العقدة تملك مفاتيح بالضبط، بحيث صارت الآن ذات مفاتيح، ويجب أن تُمنح رصيدًا واحدًا ننشئه. وفي كلتا الحالتين—سواء انتهى الحذف بعملية استعارة أم لا—لا يلزم إنشاء أكثر من ثلاثة أرصدة أثناء استدعاء للحفاظ على ثابت الأرصدة ودفع كلفة كل عمليات الاستعارة والدمج التي تحدث. وهذا يُكمل إثبات المتراجمة. والغرض من المتراجمة 14.1 هو أن نبيّن أن كلفة عمليات التقسيم والدمج والانضمام (joins) أثناء تسلسل من من عمليات و في نموذج word-RAM ليست سوى . أي أن الكلفة المُطفأة لكل عملية ليست سوى ، ومن ثمّ فالكلفة المُطفأة لطريقة و في نموذج word-RAM هي . ويُلخّص هذا بالثنائيتين التاليتين من المبرهنات: المبرهنة 14.1 (أشجار في الذاكرة الخارجية) تنفّذ BTree واجهة SSet. وفي نموذج الذاكرة الخارجية، تدعم BTree العمليات و و في زمن لكل عملية.
المبرهنة 14.2 (أشجار في word-RAM) تنفّذ BTree واجهة SSet. وفي نموذج word-RAM، ومع تجاهل كلفة عمليات التقسيم والدمج والاستعارة، تدعم BTree العمليات و و في زمن لكل عملية. وإلى جانب ذلك، فإن البدء بـ BTree فارغة وتنفيذ أي تسلسل من من عمليات و ينتج عن ذلك زمن إجمالي قدره يُنفق في تنفيذ عمليات التقسيم والدمج والاستعارة.
14.3 مناقشة والتمارين
قدَّم Aggarwal وVitter [4] نموذج الذاكرة الخارجية للحساب. وهو ما يُسمّى أحيانًا أيضًا نموذج الإدخال/الإخراج (I/O model) أو نموذج الوصول إلى القرص (disk access model). أشجار هي بالنسبة إلى البحث في الذاكرة الخارجية ما أشجار البحث الثنائية هي بالنسبة إلى البحث في الذاكرة الداخلية. وقد قدَّم Bayer وMcCreight [9] أشجار سنة 1970، وبعد أقل من عشر سنوات فقط، أشار عنوان مقالة Comer في مجلة ACM Computing Surveys إليها بأنها «حاضرة في كل مكان» (ubiquitous) [15]. وكما في أشجار البحث الثنائية، هناك اشتقاقات كثيرة لأشجار ، منها أشجار وأشجار وأشجار المُعدَّدة (counted). وأشجار هي بالفعل حاضرة في كل مكان، وهي بنية البيانات الأساسية في كثير من أنظمة الملفات، ومنها HFS+ من Apple وNTFS من Microsoft وExt4 من Linux؛ وفي كل أنظمة قواعد البيانات الكبرى؛ وفي مخازن المفتاح-القيمة (key-value stores) المستخدَمة في الحوسبة السحابية. ويقدّم استطلاع Graefe الأخير [36] عرضًا يتجاوز 200 صفحة للتطبيقات والاشتقاقات والتحسينات العديدة الحديثة لأشجار . وتنفّذ أشجار واجهة SSet. فإذا كانت الحاجة إلى واجهة USet وحدها، فيمكن استعمال التجزئة في الذاكرة الخارجية (external memory hashing) بديلًا عن أشجار . وهناك فعلًا مخطّطات للتجزئة في الذاكرة الخارجية؛ انظر، على سبيل المثال، Jensen وPagh [43]. وتنفّذ هذه المخطّطات عمليات USet في زمن متوقع قدره في نموذج الذاكرة الخارجية. غير أن تطبيقات كثيرة، ولأسباب متنوّعة، ما زالت تستعمل أشجار رغم أنها لا تتطلّب سوى عمليات USet. وأحد أسباب شعبية أشجار أنها غالبًا ما تعمل أداءً أفضل مما توحي به حدود زمن تنفيذها البالغة . والسبب في ذلك هو أن قيمة في سياقات الذاكرة الخارجية تكون عادةً كبيرة جدًّا—بالمئات أو حتى بالآلاف. وهذا يعني أن 99% أو حتى 99.9% من البيانات في شجرة مخزَّنة في الأوراق. وفي نظام قواعد بيانات بذاكرة كبيرة، قد يكون من الممكن تخزين مؤقّت (cache) لعقد شجرة الداخلية كلها في RAM، لأنها لا تمثّل سوى 1% أو 0.1% من مجموعة البيانات الكلية. وحين يحدث هذا، يعني ذلك أن البحث في شجرة ينطوي على بحث سريع جدًّا في RAM عبر العقد الداخلية، يليه وصول واحد إلى الذاكرة الخارجية لاسترجاع ورقة. التمرين 14.1 بيّن ما يحدث عند إضافة المفتاحين 1.5 ثم 7.5 إلى شجرة في الشكل 14.2.
التمرين 14.2 بيّن ما يحدث عند حذف المفتاح 3 ثم المفتاح 4 من شجرة في الشكل 14.2.
التمرين 14.3 ما أكبر عدد من العقد الداخلية في شجرة تخزّن مفتاحًا (بوصفها دالة في و )؟
التمرين 14.4 يدّعي مقدّمة هذا الفصل أن أشجار لا تحتاج سوى ذاكرة داخلية بحجم . غير أن التنفيذ المعروض هنا يحتاج فعلًا إلى ذاكرة أكبر. بيّن أن التنفيذ المعطى هنا لطريقة و يستخدم ذاكرة داخلية متناسبة مع . وصِف كيف يمكن تعديل هاتين الطريقتين من أجل خفض استهلاكهما للذاكرة إلى .
التمرين 14.5 ارسم الأرصدة المستخدَمة في إثبات المتراجمة 14.1 على الشجرتين في الشكلين 14.6 و14.7. وتحقّق من أنه (بإضافة ثلاثة أرصدة) من الممكن دفع كلفة عمليات التقسيم والدمج والاستعارة والحفاظ على ثابت الأرصدة.
التمرين 14.6 صمّم نسخة معدَّلة من شجرة يكون فيها للعقد ما بين و ابنًا (ومن ثمّ ما بين و مفتاحًا). بيّن أن هذا الإصدار الجديد من أشجار لا ينفّذ سوى من عمليات التقسيم والدمج والاستعارة أثناء تسلسل من عملية. (تلميح: لكي ينجح هذا، سيكون عليك أن تكون أكثر جرأة في الدمج، أحيانًا بدمج عقدتين قبل أن تكون الضرورة تقتضي ذلك صراحةً.)
التمرين 14.7 في هذا التمرين، ستصمّم طريقة معدَّلة للتقسيم والدمج في أشجار تقلّل عدد عمليات التقسيم والاستعارة والدمج قسميًا (asymptotically) بالنظر في ثلاث عقد في كل مرة على الأكثر. ليكن عقدة تتجاوز طاقتها، وليكن شقيقًا يقع مباشرةً إلى يمين . وهناك طريقتان لإصلاح الامتلاء الزائد عند : يمكن أن تعطي بعض مفاتيحها إلى ؛ أو يمكن تقسيم وتوزيع مفاتيح و بالتساوي على و والعقدة المُنشأة حديثًا، . بيّن أن هذا يمكن فعله دائمًا بحيث، بعد العملية، تمتلك كلٌّ من العقد المتأثّرة (وعددها 3 على الأكثر) ما لا يقل عن مفتاحًا ولا يزيد عن مفتاحًا، لأجل ثابت ما . ليكن عقدة تقلّ عن طاقتها، وليكن و شقيقَي . وهناك طريقتان لإصلاح النقص عند : يمكن إعادة توزيع المفاتيح بين و و ؛ أو يمكن دمج و و في عقدتين وإعادة توزيع مفاتيح و و على هذه العقد. بيّن أن هذا يمكن فعله دائمًا بحيث، بعد العملية، تمتلك كلٌّ من العقد المتأثّرة (وعددها 3 على الأكثر) ما لا يقل عن مفتاحًا ولا يزيد عن مفتاحًا، لأجل ثابت ما . بيّن أنه مع هذه التعديلات، يكون عدد عمليات الدمج والاستعارة والتقسيم التي تحدث أثناء عملية هو .
التمرين 14.8 شجرة ، والمبيَّنة في الشكل 14.11، تخزّن كل مفتاح في ورقة وتحتفظ بأوراقها مخزَّنة في قائمة مترابطة مزدوجة (doubly-linked list). وكالمعتاد، تخزّن كل ورقة ما بين و مفتاحًا. وفوق هذه القائمة توجد شجرة معيارية تخزّن أكبر قيمة من كل ورقة عدا الأخيرة. صِف تنفيذات سريعة لطريقة و و في شجرة . واشرح كيفية تنفيذ طريقة بكفاءة، وهي التي تُبلّغ عن كل القيم الأكبر من والأصغر من أو المساوية لها، في شجرة . نفّذ صنفًا هو BPlusTree ينفّذ و و و . وتكرّر أشجار بعض المفاتيح لأنها مخزَّنة في شجرة وفي القائمة معًا. واشرح لماذا لا يكون هذا التكرار كبيرًا مع قيم الكبيرة.