لماذا تقوم قواعد البيانات باستخدام الb+ tree بدلاً من hashtable

الhash table (جدول التشفير) يعمل بالشكل التالي

1. يتم عمل عملية hashing للمفتاح
2. يتم تخزين قيمة المفتاح في الذاكرة في العنوان الذي حصلنا عليه من عملية الhashing
3. عندما نريد الحصول على القيمة المُخزنة في قاعدة البيانات نقوم بكُل بساطة بعملية hashing للمفتاح الذي نريد الحصول على قيمته
4. ومن ثم نذهب للذاكرة في العنوان الذي حصلنا عليه من عملية الhashing ونأتي بالقيمة

عملية بسيطة والتعقيد الوقتي لها (Time complexity) أقل نوع وهو الثابت O(1)  

بالنسبة للأشجار(trees) فيتم فيها تخزين العناصر بشكل مرتب وعندما نريد الحصول على عنصر معين نقوم بالنظر في منتصف العناصر, إن كان العنصر المحصول عليه أكبر من المُراد نبحث في الجزأ الأيسر من العناصر( على فرض أن العناصر في الشجرة مرتبة من اليسار لليمين بشكلٍ تصاعدي) , إن كان العنصر أصغر نبحث في الجزأ الأيمن.

تلك العملية في المتوسط تأخذ وقت O(logn) 

حسنا لماذا إذا نقوم بإستخدام الأشجار بدلاً من الجداول؟ ببساطة لأن بسبب أن الجداول تتعامل بعنوان الذاكرة وليس ترتيب معين للعناصر يوجد بعض العمليات التي تكون غير عملية بإستخدام الجداول, مثلاً ﻻ نستطيع أن نعثر على جميع العناصر الأقل من قيمة معينة أو أكبر من قيمة معينة, ﻻ نستطيع العثور عﻻ جميع العناصر بين قيمتين 

select * where id >5000
select * where id between(1000, 2000)
select all where id <1000

كل تلك العمليات تكون غير عملية بالمرة بالنسبة للجدول , بالإضافة لعمليات الترتيب التي تكون مجهدة

بالنسبة للأشجار لأنها تتعامل مع العناصر مرتبة وتخزن العناصر على هيئة قائمة وليس على اساس عنوان في الذاكرة فيكون تلك العمليات سهلة , فنضحي بشئٍ من السرعة مقابل الكثير من المرونة .