المستوى: محترف — يفترض إنك تعرف Big-O وLinked Lists وBinary Search Trees وأساسيات الاحتمال.
لو الـ leaderboard بتاعك في Redis ZSET فيه 10 مليون لاعب وعايز ترجّع أعلى 100 score، Redis بيرد في 0.3 مللي ثانية. مش لأن السيرفر سريع — لأن الهيكل اللي ورا ZSET اسمه Skip List، وبيرفض إنه يكون شجرة متوازنة كاملة (AVL أو Red-Black). بدلاً من ذلك بيعمل balancing احتمالي، فالكود أبسط بكثير والأداء يساوي O(log n) متوقّع.
Skip List: ازاي بنية بيانات احتمالية بتغلب الأشجار المتوازنة في الإنتاج
المشكلة باختصار
تخيّل عندك Linked List مرتّبة فيها مليون عنصر. البحث عن عنصر بـ score = 12,847 معناه إنك بتعدّي على نص العناصر متوسطًا — يعني O(n). الحل التقليدي: Red-Black Tree أو AVL Tree. النتيجة O(log n)، بس الكود مرعب: rotations يمين/شمال، تلوين عقد، حالات edge cases بتمشي على 200 سطر للـ insert لوحده.
William Pugh في ورقته الشهيرة "Skip Lists: A Probabilistic Alternative to Balanced Trees" (CACM, June 1990) قدّم بديل بسيط: linked list من طبقات. الطبقة السفلى فيها كل العناصر. كل طبقة فوقها بتتجاهل تقريبًا نص العناصر بشكل عشوائي. النتيجة: بحث وإدراج وحذف بـ O(log n) متوقّع، بدون أي rotation.
تشبيه للمستوى المبتدئ: قطار سريع بمحطات قليلة
تخيّل خط مترو فيه 100 محطة. اللي يعدّي على كل محطة بطيء جدًا. اللي معاه قطار "سريع" بيقف كل 4 محطات بس، بيوصل في ربع الزمن. اللي معاه قطار "أسرع" بيقف كل 16 محطة، أسرع لكن خطواته أكبر. Skip List هو نفس المبدأ بالظبط: طبقات متعدّدة من الـ pointers بتسمح بقفزات كبيرة في الأول، وبعد كده تنزل لطبقة أدق لمّا تقرب من الهدف. كل ما تنزل طبقة، الدقة بتزيد والسرعة بتقلّ.
التعريف العلمي الدقيق
الـ Skip List بنية بيانات احتمالية مكوّنة من L طبقات (level 0 لـ level L-1). كل عنصر بياخد level عشوائي مبني على توزيع هندسي بـ probability factor p. احتمال إن العنصر يكون في level k = pk. في Redis تحديدًا p = 0.25 وL = 32 (راجع t_zset.c في كود Redis 7.x).
البحث بيبدأ من أعلى طبقة في أقصى يسار وبيتقدّم يمين طول ما الـ score الجاي أصغر من الهدف. لو الجاي أكبر، ينزل طبقة. الـ expected search time = O(log n / log(1/p)). مع p=0.25، الثابت أكبر شوية من p=0.5 لكن الذاكرة المستهلكة أقل بحوالي 33%.
كود Python شغّال في 50 سطر
import random
class Node:
__slots__ = ("score", "value", "forward")
def __init__(self, score, value, level):
self.score = score
self.value = value
self.forward = [None] * (level + 1)
class SkipList:
P = 0.25
MAX_LEVEL = 32
def __init__(self):
self.head = Node(float("-inf"), None, self.MAX_LEVEL)
self.level = 0
def _random_level(self):
lvl = 0
while random.random() < self.P and lvl < self.MAX_LEVEL:
lvl += 1
return lvl
def insert(self, score, value):
update = [self.head] * (self.MAX_LEVEL + 1)
cur = self.head
for i in range(self.level, -1, -1):
while cur.forward[i] and cur.forward[i].score < score:
cur = cur.forward[i]
update[i] = cur
lvl = self._random_level()
if lvl > self.level:
self.level = lvl
node = Node(score, value, lvl)
for i in range(lvl + 1):
node.forward[i] = update[i].forward[i]
update[i].forward[i] = node
def top_k(self, k):
result, cur = [], self.head.forward[0]
while cur and len(result) < k:
result.append((cur.score, cur.value))
cur = cur.forward[0]
return result
