# ساختار داده جستجو
در علوم کامپیوتر، یک ساختار داده جستجو (به انگلیسی: Search Data Structure) نوعی ساختمان داده‌ها است که امکان بازیابی کارآمد آیتم‌های خاص را از مجموعه‌ای از آیتم‌ها فراهم می‌کند؛ مانند بازیابی یک رکورد یا ساختار (علم کامپیوتر) مشخص از یک پایگاه داده.
ساده‌ترین، عمومی‌ترین و در عین حال ناکارآمدترین ساختار دادهٔ جستجو، تنها یک فهرست ترتیبی نامرتب از همهٔ اعضاست. یافتن عضو مورد نظر در چنین فهرستی، با استفاده از روش جستجوی خطی، ناگزیر به تعداد عملیاتی متناسب با تعداد اعضا (n) نیاز دارد؛ چه در بدترین حالت و چه در حالت متوسط. ساختارهای دادهٔ جستجوی مفیدتر، امکان بازیابی سریع‌تر را فراهم می‌کنند؛ با این حال، تنها به انواع خاصی از جستجو محدود هستند. افزون بر این، از آنجا که هزینهٔ ساخت این ساختارها دست‌کم متناسب با n است، استفاده از آن‌ها فقط زمانی مقرون‌به‌صرفه خواهد بود که قرار باشد چندین جستجو روی یک پایگاه داده (یا پایگاه داده‌ای که بین دو جستجو تغییر چندانی نمی‌کند) انجام شود.
ساختارهای دادهٔ جستجوی ایستا برای پاسخ‌دهی به تعداد زیادی درخواست (کوئری) بر روی یک پایگاه داده ثابت طراحی شده‌اند؛ درحالی‌که ساختارهای پویا امکان درج، حذف یا به‌روزرسانی داده‌ها را میان درخواست‌های متوالی فراهم می‌کنند. در حالت پویا، باید هزینهٔ اصلاح ساختار جستجو برای سازگار شدن با تغییرات پایگاه داده را نیز مدنظر قرار داد.

## رده‌بندی
ساده‌ترین نوع کوئری این است که یک رکورد را بیابیم که مقدار یک فیلد خاص (یعنی کلید) آن برابر با مقدار معینی (v) باشد. انواع رایج دیگر کوئری عبارت‌اند از: «یافتن عضوی با کمترین (یا بیشترین) مقدار کلید»، «یافتن رکوردی با بیشترین مقدار کلید که از v بزرگ‌تر نباشد»، و «یافتن تمام اعضایی که مقدار کلید آن‌ها بین دو حد مشخص vmin و vmax باشد».
در برخی از پایگاه داده‌ها، مقادیر کلید ممکن است نقاطی در یک (فضای چندبعدی) باشند. برای مثال، کلید می‌تواند یک موقعیت جغرافیایی (مانند عرض جغرافیایی و طول جغرافیایی) بر روی زمین باشد. در این حالت، انواع رایج کوئری‌ها عبارتند از: «یافتن رکوردی با کلیدی که نزدیک‌ترین به یک نقطهٔ معین v باشد»، یا «یافتن همهٔ آیتم‌هایی که کلید آن‌ها در فاصلهٔ مشخصی از v قرار دارد»، یا «یافتن همهٔ آیتم‌ها در یک ناحیهٔ معین R از این فضا».
یک حالت خاص رایج از گونهٔ اخیر، کوئری‌های بازه‌ای همزمان روی دو یا چند کلید ساده است؛ برای مثال: «یافتن همهٔ رکوردهای کارمندان با حقوق بین ۵۰٬۰۰۰ تا ۱۰۰٬۰۰۰ و تاریخ استخدام بین سال‌های ۱۹۹۵ تا ۲۰۰۷».
یک مورد خاص رایج از حالت دوم، کوئری‌های دامنه همزمان روی دو یا چند کلید ساده است؛ مانند «یافتن تمام رکوردهای کارمندان با حقوق بین ۵۰٬۰۰۰ و ۱۰۰٬۰۰۰ و استخدام بین سال‌های ۱۹۹۵ و ۲۰۰۷».

### کلیدهای مرتب منفرد
- آرایه (در صورتی که مقادیر کلیدها در یک بازهٔ نسبتاً متراکم قرار داشته باشند)
- فهرست مرتب بر اساس اولویت؛ (نگاه کنید به جستجوی خطی)
- آرایه مرتب‌شده بر حسب کلید؛ (نگاه کنید به جستجوی دودویی)
- درخت جستجوی دودویی خود-متوازن
- جدول درهم‌سازی


### یافتن کوچک‌ترین عضو
- هیپ


## تحلیل حدی در بدترین حالت
در این جدول، نماد مجانبی {\displaystyle O(f(n))} به این معناست که «در بدترین حالت، مقدار از چندبرابر ثابتی از {\displaystyle f(n)} بیشتر نمی‌شود.»
| ساختار داده                   | درج      | حذف      | تعادل‌یابی | دسترسی به اندیس | جستجو     | یافتن کمینه                               | یافتن بیشینه                              | مصرف حافظه |
| ----------------------------- | -------- | -------- | --------- | --------------- | --------- | ----------------------------------------- | ----------------------------------------- | ---------- |
| آرایه نامرتب                  | O(1)     | O(1)     | N/A       | O(1)            | O(n)      | O(n)                                      | O(n)                                      | O(n)       |
| آرایه مرتب                    | O(n)     | O(n)     | N/A       | O(1)            | O(log n)  | O(1)                                      | O(1)                                      | O(n)       |
| پشته                          | O(1)     | O(1)     |           |                 | O(n)      |                                           |                                           | O(n)       |
| صف                            | O(1)     | O(1)     |           |                 | O(n)      |                                           |                                           | O(n)       |
| لیست پیوندینامرتب             | O(1)     | O(1)     | N/A       | O(n)            | O(n)      | O(n)                                      | O(n)                                      | O(n)       |
| لیست پیوندی مرتب              | O(n)     | O(1)     | N/A       | O(n)            | O(n)      | O(1)                                      | O(1)                                      | O(n)       |
| فهرست پرشی                    |          |          |           |                 |           |                                           |                                           |            |
| درخت جستجوی دودویی خود-متوازن | O(log n) | O(log n) | O(log n)  | N/A             | O(log n)  | O(log n)                                  | O(log n)                                  | O(n)       |
| هیپ                           | O(log n) | O(log n) | O(log n)  | N/A             | O(n)      | O(1) برای هیپ کمینه، O(n) برای هیپ بیشینه | O(1) برای هیپ بیشینه، O(n) برای هیپ کمینه | O(n)       |
| جدول درهم‌سازی                 | O(1)     | O(1)     | O(n)      | N/A             | O(1)      | O(n)                                      | O(n)                                      | O(n)       |
| تری (k = میانگین طول کلید)    | O(k)     | O(k)     | N/A       | O(k)            | O(k)      | O(k)                                      | O(k)                                      | O(k n)     |
| درخت دکارتی                   |          |          |           |                 |           |                                           |                                           |            |
| درخت B                        | O(log n) | O(log n) | O(log n)  | N/A             | O(log n)  | O(log n)                                  | O(log n)                                  | O(n)       |
| درخت سرخ-سیاه                 | O(log n) | O(log n) |           |                 | O(log n)  |                                           |                                           | O(n)       |
| درخت گسترده                   |          |          |           |                 |           |                                           |                                           |            |
| درخت AVL                      |          |          |           |                 | O(\log n) |                                           |                                           |            |
| درخت k-بعدی                   |          |          |           |                 |           |                                           |                                           |            |

در برخی منابع، درج (insert) در یک آرایه نامرتب، به صورت O(n) بیان می‌شود؛ زیرا فرض بر این است که عنصر جدید باید در یک موقعیت خاص از آرایه قرار گیرد که این کار مستلزم جابه‌جایی تمامی عناصر بعدی به اندازهٔ یک خانه است. اما در یک آرایهٔ کلاسیک، آرایه برای نگهداری عناصر دلخواه و نامرتب استفاده می‌شود و محل دقیق هر عنصر اهمیتی ندارد؛ بنابراین درج معمولاً با افزایش اندازهٔ آرایه به اندازهٔ یک و قراردادن عنصر جدید در انتهای آرایه انجام می‌شود که این، عملیات O(1) است. در برخی منابع انگلیسی برای حالت درج در آرایهٔ نامرتب دو حالت بیان شده است که بسته به نوع پیاده‌سازی تفاوت دارد. جهت توضیح بیشتر به یادداشت‌های جدول مراجعه شود.
همچنین، عملیات حذف (delete) گاهی به صورت O(n) بیان می‌شود، چرا که ممکن است فرض شود بعد از حذف باید عناصر بعدی جابه‌جا شوند. ولی در آرایهٔ نامرتب کلاسیک، ترتیب عناصر اهمیتی ندارد (هرچند عناصر به‌طور ضمنی به ترتیب زمان درج مرتب‌اند)، لذا حذف می‌تواند با جابه‌جایی عنصر مورد نظر با آخرین عنصر آرایه و سپس کاهش اندازهٔ آرایه به اندازهٔ یک انجام شود که این هم O(1) است.
این جدول صرفاً یک خلاصه تقریبی است؛ برای هر ساختار داده، حالت‌ها و گونه‌های خاصی وجود دارد که ممکن است هزینه‌ها را تغییر دهد. همچنین، با ترکیب دو یا چند ساختار داده می‌توان به هزینه‌های کم‌تری رسید.