ساختار داده جستجو
این مقاله به دلیل زیر نامزد حذف زماندار شده است:
اگر میتوانید مشکل این مقاله را با ویرایش، نگارش، منبعدهی، تغییر نام یا ادغام حل کنید، لطفاً این صفحه را ویرایش کنید و مقاله را در حد استانداردهای ویکیپدیا بهبود دهید. در صورتی که مقاله را بهبود بخشیدید، میتوانید این برچسب را بردارید یا این که با هر دلیلی با حذف صفحه مخالفت کنید. اما اگر خودتان سازندهٔ این مقاله هستید، لطفاً این برچسب را از مقاله برندارید و از کاربری دیگر یا نامزدکننده بخواهید تا برچسب را بردارد. اگرچه الزامی وجود ندارد، اما توصیه میشود که دلیل خود برای مخالفت را در خلاصهٔ ویرایش یا در صفحهٔ بحث مقاله ذکر کنید. اگر این الگو حذف شد، آن را دوباره در صفحه قرار ندهید. این پیام برای بیش از ده روز در جای خود باقی مانده است، بنابراین ممکن است مقاله بدون هیچ اعلان دیگری حذف شود. یافتن منابع: "ساختار داده جستجو" – اخبار · روزنامهها · کتابها · آکادمیک · جیاستور برچسب زمان: 20240619185604 ۱۹ ژوئن ۲۰۲۴، ساعت ۱۸:۵۶ (UTC) برای مدیران: حذف صفحه |
در علوم کامپیوتر، ساختار داده جستجو هر ساختار داده ای است که امکان بازیابی کارآمد موارد خاص را از مجموعه ای از موارد، مانند یک رکورد خاص از یک پایگاه داده را ایجاد می کند.
ساختارهای جستجوی ایستا برای پاسخ دادن به کوئری های زیادی در یک پایگاه داده ثابت طراحی شده اند. ساختارهای پویا همچنین اجازه درج، حذف یا اصلاح موارد را بین کوئری های متوالی می دهند. در مورد پویا، باید هزینه تعمیر ساختار جستجو را برای محاسبه تغییرات در پایگاه داده نیز در نظر گرفت.
طبقه بندی
[ویرایش]ساده ترین نوع کوئری این است که رکوردی را بیابید که دارای یک فیلد خاص (کلید) برابر با مقدار مشخص v باشد. سایر انواع رایج کوئری ها عبارتند از "یافتن آیتم با کوچکترین (یا بزرگترین) مقدار کلید"، "یافتن آیتم با بزرگترین مقدار کلید که از v بزرگتر نباشد "همه موارد با مقادیر کلیدی بین مرزهای مشخص شده vmin و vmax ".
در بعضی پایگاههای داده، مقادیر کلید ممکن است نقاطی در یک فضای چند بعدی باشند. به عنوان مثال، ممکن است کلید یک موقعیت جغرافیایی (عرض جغرافیایی و طول جغرافیایی) روی زمین باشد. در این صورت، انواع متداول کوئری ها عبارتند از "یافتن رکورد با یک کلید در نزدیکترین فاصله از نقطه داده شده v"، یا "یافتن تمام مواردی که کلید آنها در فاصلهای مشخص از v قرار دارد"، یا "یافتن تمام موارد داخل منطقه مشخص R از فضای داده".
یک مورد خاص رایج برای حالت دوم، کوئری های همزمان در محدوده بر روی دو یا تعدادی بیشتر کلید ساده است، مانند "یافتن همه رکوردهای کارمندهایی با حقوق بین50,000 و 100,000 و استخدام شده بین سال های 1995 و 2007".
منابع
[ویرایش]- Thomas H, Cormen; Charles E, Leiserson; Ronald L, Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 978-0-262-53091-0.
LIST-DELETE runs in O(1) time, but if to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH.
- Sherrod, Allen (2007). Data Structures and Algorithms for Game Developers. Cengage Learning. ISBN 978-1-58450-663-8.
The insertion of an item into an unordered array does not depend on anything other than placing the new item at the end of the list. This gives the insertion into an unordered array of O(1).