الوحدة 9: مقايضات المساحة والوقت (التهشير وأشجار B)
تغطي هذه الوحدة مفاهيم التهشير (Hashing) كطريقة فعالة لتنفيذ القواميس، واستراتيجيات حل التصادم، بالإضافة إلى أشجار B (B-Trees) كأداة رئيسية لفهرسة البيانات.
Module 9: Space and Time Trade-Offs (Hashing and B-Trees)
This module covers Hashing as an efficient method for implementing dictionaries, collision resolution strategies, and B-Trees as a principal device for data indexing.
أهداف التعلم
- تطبيق التهشير (Hashing) في مجالات المشاكل المختلفة.
- وصف أشجار B (B-Trees) وخصائصها الهيكلية.
- تحليل كفاءة استراتيجيات حل التصادم المختلفة في التهشير.
- Apply Hashing in various problem domains.
- Describe B-Trees and their structural properties.
- Analyze the efficiency of different collision resolution strategies in hashing.
1 أساسيات التهشير (Hashing)
1 Hashing Basics
التهشير هو طريقة فعالة لتنفيذ قاموس باستخدام دالة رياضية لتعيين المفاتيح إلى مواقع في جدول. يشبه الأمر استخدام فهرس أبجدي للوصول السريع إلى كتاب في مكتبة.
Hashing is an efficient method for implementing a dictionary by mapping keys to locations in a table using a function. It's like using an alphabetical index to quickly find a book.
تعتمد فكرة التهشير على تعيين مفاتيح ملف بحجم $n$ إلى جدول بحجم $m$ (يسمى جدول التهشير) باستخدام دالة محددة مسبقاً تسمى دالة التهشير $h(K)$.
يجب أن تكون دالة التهشير الجيدة سهلة الحساب وتوزع المفاتيح بالتساوي تقريباً في جميع أنحاء الجدول.
من التطبيقات المهمة للتهشير: جداول الرموز وقواعد البيانات.
The idea of hashing is to map keys of a given file of size $n$ into a table of size $m$ (called the hash table) by using a predefined function, called the hash function $h(K)$.
A good hash function should be easy to compute and distribute keys about evenly throughout the hash table.
Important applications include symbol tables and databases.
يعتمد التهشير على أفكار تغيير التمثيل ومقايضة المساحة بالوقت (space-for-time tradeoff).
من خلال تخصيص مساحة إضافية (جدول التهشير)، نحقق أوقات بحث وإدراج وحذف تقترب من $O(1)$ في المتوسط.
Hashing is based on representation-change and space-for-time tradeoff ideas.
By allocating extra space (the hash table), we achieve search, insert, and delete operations in $O(1)$ time on average.
لماذا يُفضل أن يكون حجم جدول التهشير (m) عدداً أولياً في دالة (K mod m)؟ Why is it preferred for the hash table size (m) to be a prime number in the (K mod m) function?
يساعد استخدام عدد أولي في تقليل التصادمات من خلال توزيع المفاتيح بشكل أكثر توازناً، خاصة إذا كانت المفاتيح تشترك في عوامل مشتركة.
Using a prime number helps reduce collisions by distributing keys more evenly, especially if the keys share common factors.
2 التصادمات والتهشير المفتوح (السلسلة المنفصلة)
2 Collisions and Open Hashing (Separate Chaining)
يحدث التصادم عندما يتم تعيين مفتاحين لنفس الموقع. التهشير المفتوح يحل ذلك بتخزين المفاتيح في قوائم مرتبطة خارج الجدول.
A collision occurs when two keys map to the same location. Open hashing solves this by storing keys in linked lists outside the table.
إذا كان $h(K_1) = h(K_2)$، فهناك تصادم. حتى مع الدوال الجيدة، يُتوقع حدوث تصادمات (مفارقة عيد الميلاد).
في التهشير المفتوح (السلسلة المنفصلة)، يتم تخزين المفاتيح في قوائم مرتبطة خارج جدول التهشير، حيث تعمل عناصر الجدول كرؤوس لهذه القوائم.
إذا وزعت الدالة المفاتيح بشكل موحد، فإن متوسط طول القائمة المرتبطة سيكون $\alpha = n/m$ (عامل التحميل).
لا يزال التهشير المفتوح يعمل حتى لو كان عدد المفاتيح أكبر من حجم الجدول ($n > m$).
If $h(K_1) = h(K_2)$, there is a collision. Even with good functions, collisions should be expected (birthday paradox).
In Open hashing (Separate chaining), keys are stored in linked lists outside a hash table whose elements serve as the lists' headers.
If the function distributes keys uniformly, the average length of the linked list is $\alpha = n/m$ (load factor).
Open hashing still works if $n > m$.
كفاءة العمليات (البحث، الإدراج، الحذف) متطابقة، وهي جميعها $O(1)$ في الحالة المتوسطة إذا كان عدد المفاتيح $n$ مساوياً تقريباً لحجم الجدول $m$.
يتم الاحتفاظ بعامل التحميل $\alpha$ صغيراً (حوالي 1 بشكل مثالي).
The efficiency of these operations is identical to that of searching, and they are all $O(1)$ in the average case if the number of keys $n$ is about equal to the hash table's size $m$.
Load $\alpha$ is typically kept small (ideally, about 1).
ماذا يحدث لأداء التهشير المفتوح إذا أصبح عامل التحميل كبيراً جداً؟ What happens to the performance of open hashing if the load factor becomes very large?
تصبح القوائم المرتبطة طويلة جداً، مما يؤدي إلى تدهور وقت البحث ليقترب من O(n) بدلاً من O(1).
The linked lists become very long, degrading the search time to approach O(n) instead of O(1).
3 التهشير المغلق (العنونة المفتوحة)
3 Closed Hashing (Open Addressing)
في التهشير المغلق، يتم تخزين جميع المفاتيح داخل الجدول نفسه بدون مؤشرات. إذا كان المكان مشغولاً، نبحث عن المكان التالي المتاح.
In closed hashing, all keys are stored inside the table itself without pointers. If a spot is taken, we look for the next available one.
يتم تخزين المفاتيح داخل جدول التهشير نفسه دون استخدام القوائم المرتبطة.
يجب أن يكون حجم الجدول $m$ على الأقل بحجم عدد المفاتيح $n$.
لحل التصادم، يمكن استخدام استراتيجيات مثل الفحص الخطي (linear probing) حيث يتم التحقق من الخلية التالية، وإذا وصلنا لنهاية الجدول نعود للبداية (مصفوفة دائرية).
استراتيجية أخرى هي التهشير المزدوج (double hashing) التي تستخدم دالة تهشير ثانية لحساب مقدار الزيادة.
Keys are stored inside a hash table itself without the use of linked lists.
The table size $m$ must be at least as large as the number of keys $n$.
For collision resolution, strategies like linear probing check the next cell, wrapping around to the beginning if the end is reached.
Another strategy is double hashing, which uses a second hash function to compute the increment.
التهشير المغلق يتجنب استخدام المؤشرات، لكنه لا يعمل إذا كان $n > m$.
عمليات الحذف ليست مباشرة (تتطلب علامات خاصة).
كلما امتلأ الجدول (اقترب $\alpha$ من 1)، يزداد عدد الفحوصات في الفحص الخطي بشكل كبير.
Closed hashing avoids pointers but does not work if $n > m$.
Deletions are not straightforward.
As the table gets filled ($\alpha$ approaches 1), the number of probes in linear probing increases dramatically.
| Open Hashing (Separate Chaining) | Closed Hashing (Open Addressing) | |
|---|---|---|
| مكان تخزين المفاتيحKey Storage Location | خارج الجدول (قوائم مرتبطة)Outside table (Linked lists) | داخل الجدول نفسهInside the table itself |
| العمل عندما n > mWorks when n > m | نعم، يعملYes, it works | لا يعملDoes not work |
| استخدام المؤشراتPointer Usage | يستخدم المؤشراتUses pointers | يتجنب المؤشراتAvoids pointers |
| سهولة الحذفEase of Deletion | مباشر وسهلStraightforward | غير مباشر (معقد)Not straightforward |
لماذا تعتبر عملية الحذف في التهشير المغلق غير مباشرة (Not straightforward)؟ Why are deletions in closed hashing not straightforward?
لأن إزالة عنصر ببساطة قد يكسر سلسلة البحث عن عناصر أخرى تم إزاحتها بسبب التصادم. يتطلب الأمر وضع علامة (Tombstone) تدل على أن الخلية كانت مشغولة وحُذفت.
Because simply removing an element might break the search chain for other elements displaced by collisions. It requires placing a special marker (Tombstone) indicating the cell was occupied but deleted.
4 أشجار B وخصائصها
4 B-Trees and Properties
شجرة B هي شجرة بحث متوازنة تسمح بتخزين مفاتيح متعددة في نفس العقدة، وهي مثالية لفهرسة البيانات على الأقراص.
A B-tree is a balanced search tree that allows multiple keys in the same node, ideal for indexing data on disks.
أشجار B هي أداة رئيسية لتنظيم مجموعات البيانات كفهرس. تسمح بأكثر من مفتاح واحد في نفس العقدة.
في إصدار B-tree، يتم تخزين جميع سجلات البيانات في الأوراق بترتيب تصاعدي. العقد الأبوية تُستخدم للفهرسة وتحتوي على $n-1$ مفاتيح مرتبة.
خصائص شجرة B من الرتبة $m \ge 2$:
- الجذر إما ورقة أو له بين 2 و $m$ أبناء.
- كل عقدة (باستثناء الجذر والأوراق) لها بين $\lceil m/2 \rceil$ و $m$ أبناء.
- الشجرة متوازنة تماماً (جميع الأوراق في نفس المستوى).
B-trees are a principal device for organizing data sets as an index. They permit more than a single key in the same node.
In the B-tree version, all data records are stored at the leaves in increasing order. Parental nodes are used for indexing and contain $n-1$ ordered keys.
Properties of a B-tree of order $m \ge 2$:
- The root is either a leaf or has between 2 and $m$ children.
- Each node (except root and leaves) has between $\lceil m/2 \rceil$ and $m$ children.
- The tree is perfectly balanced (all leaves at the same level).
يتم تداخل المفاتيح مع $n$ مؤشرات لأبناء العقدة بحيث تكون جميع المفاتيح في الشجرة الفرعية $T_0$ أصغر من $K_1$، والمفاتيح في $T_1$ أكبر من أو تساوي $K_1$ وأصغر من $K_2$، وهكذا.
هذا التصميم يقلل بشكل كبير من عدد عمليات الوصول للقرص (Disk Accesses) للملفات الكبيرة جداً.
Keys are interposed with $n$ pointers to children so that keys in subtree $T_0$ are smaller than $K_1$, keys in $T_1$ are $\ge K_1$ and $< K_2$, and so on.
This design drastically reduces disk accesses for extremely large files.
لماذا تعتبر أشجار B أفضل من أشجار البحث الثنائية (BST) لتخزين قواعد البيانات على الأقراص الصلبة؟ Why are B-Trees better than Binary Search Trees (BST) for storing databases on hard disks?
لأن الوصول إلى القرص بطيء جداً. أشجار B تمتلك تفرعاً كبيراً (عقد واسعة) مما يقلل من ارتفاع الشجرة، وبالتالي يقلل من عدد مرات القراءة من القرص للوصول إلى البيانات.
Because disk access is very slow. B-Trees have a high branching factor (wide nodes) which minimizes the tree's height, thereby reducing the number of disk reads needed to access data.
5 البحث في أشجار B وتعقيد الوقت
5 B-Trees Searching and Time Complexity
للبحث في شجرة B، نتتبع المؤشرات من الجذر إلى الورقة المناسبة، ثم نبحث داخل العقدة. يمكن استخدام البحث الثنائي داخل العقدة لتسريع العملية.
To search a B-Tree, follow pointers from the root to the appropriate leaf, then search within the node. Binary search can be used inside the node to speed it up.
بدءاً من الجذر:
- اتبع سلسلة من المؤشرات إلى الورقة التي قد تحتوي على مفتاح البحث.
- ابحث عن المفتاح بين مفاتيح تلك الورقة.
- استخدم البحث الثنائي إذا كان عدد المفاتيح في العقدة كبيراً بما يكفي، حيث يتم تخزين المفاتيح بترتيب فرز في كل من العقد الأبوية والأوراق.
Starting with the root:
- Follow a chain of pointers to the leaf that may contain the search key.
- Search for the key among the keys of that leaf.
- Use binary search if the number of keys at a node is large enough, since keys are stored in sorted order at both parental nodes and leaves.
ارتفاع شجرة B هو $h = O(\log n)$.
بالإضافة إلى قراءات القرص، تعقيد الوقت لكل بحث خطي داخل العقدة هو $O(t)$، مما يجعل التعقيد الإجمالي $O(t \log_t n)$.
إذا تم تغيير البحث الخطي داخل كل عقدة إلى بحث ثنائي، يصبح التعقيد الإجمالي $O(\log_2 t \log_t n)$.
The height of the B-tree is $h = O(\log n)$.
In addition to disk reads, the time complexity of each linear search inside a node is $O(t)$, making total time complexity $O(t \log_t n)$.
If linear search is changed to binary search, the total time complexity is $O(\log_2 t \log_t n)$.
متى يكون استخدام البحث الخطي داخل عقدة شجرة B مقبولاً بدلاً من البحث الثنائي؟ When is it acceptable to use linear search inside a B-Tree node instead of binary search?
عندما تكون رتبة الشجرة (m) صغيرة جداً، حيث أن التكلفة الإضافية لإعداد البحث الثنائي قد تتجاوز فائدته مقارنة بالبحث الخطي السريع في مصفوفة صغيرة.
When the tree order (m) is very small, as the overhead of setting up binary search might outweigh its benefits compared to a fast linear scan of a small array.