B-Tree
![[b-tree-binary-tree.png]]
این B-tree یه ساختار داده‌ایه که برای ذخیره‌سازی و جستجوی سریع داده‌ها استفاده می‌شه. فرض کن که یه درخت داریم که گره‌هاش به‌جای نگه‌داشتن فقط یه مقدار، می‌تونن چند تا مقدار رو تو خودشون ذخیره کنن. این ویژگی به این معنیه که می‌تونیم توی یک گره، چند تا داده رو داشته باشیم و این باعث می‌شه که وقتی داریم داده‌ها رو جستجو می‌کنیم، سریع‌تر به نتیجه برسیم چون هر گره می‌تونه چند انتخاب رو به‌طور همزمان پوشش بده.
ویژگی‌های B-tree:
-
متعادل بودن: درخت همیشه متعادل می‌مونه، یعنی همه برگ‌ها (گره‌هایی که داده ذخیره می‌کنن) در یک سطح قرار دارن. این یعنی سرعت جستجو همیشه یه اندازه‌ست و زمان اجرای الگوریتم‌ها ثابت می‌مونه.
-
چند شاخه‌ای بودن: هر گره می‌تونه چند تا بچه داشته باشه، نه فقط یکی. این باعث می‌شه که تعداد گره‌ها و عمق درخت کم بشه و جستجو سریع‌تر بشه.
-
پشتیبانی از عملیات مختلف: B-tree برای جستجو، درج، و حذف داده‌ها بهینه‌سازی شده و زمان انجام این عملیات‌ها همیشه در حد مطلوبی باقی می‌مونه.
به‌طور کلی، B-tree برای سیستم‌هایی که نیاز به جستجوی سریع و مدیریت حجم زیاد داده دارن، مثل دیتابیس‌ها، خیلی مفیده. مثلاً اگر بخوایم توی یک دیتابیس بزرگ که داده‌ها مرتب شده، رکوردی رو پیدا کنیم یا حذف کنیم، B-tree کمک می‌کنه که این کار سریع و مؤثر انجام بشه.
https://www.cs.usfca.edu/~galles/visualization/BTree.html
محدودیت های B-tree
![[btree-values.png]]
-
فضای زیادی که در صورت داشتن مقادیر طولانی می‌گیره: وقتی توی هر نود هم کلید و هم مقدار ذخیره می‌شه، اگر مقدارها مثلاً UUIDهای طولانی یا داده‌های بزرگ باشن، فضای زیادی از حافظه رو اشغال می‌کنن. این موضوع می‌تونه برای سیستم‌هایی که به‌طور خاص به کارایی حافظه حساس هستن، مشکل‌ساز بشه، مخصوصاً وقتی حجم داده‌ها زیاد باشه.
-
کندی در کوئری‌های range: در جستجوهای range (یعنی جستجوهای مقادیر بین دو مقدار خاص) عملکرد B-tree می‌تونه نسبت به ساختارهای داده‌ای دیگه مثل B+ tree کندتر باشه. دلیل این کندی اینه که در B-tree هر نود می‌تونه مقادیر و کلیدهای مختلفی داشته باشه، که این باعث می‌شه برای پیدا کردن همه مقادیر داخل یک بازه، نیاز به پیمایش گره‌های بیشتری باشه. در حالی که در B+ tree، فقط کلیدها در گره‌ها ذخیره می‌شن و مقادیر در برگ‌ها (leaf nodes) قرار دارن، که می‌تونه سرعت جستجوی range رو افزایش بده.
این موارد توی [[B+Tree]] حل شده و دیتابیس های مثل پست گرس و my sql هم از این روش میرن