Content deleted Content added
Sheep8144402 (talk | contribs) fix linter error (1x missing end tag) Tags: Mobile edit Mobile web edit Advanced mobile edit |
→top: lx |
||
Line 1:
In [[computer science]], a '''search data structure'''{{citation needed|date=May 2016}} is any [[data structure]] that allows the efficient [[data retrieval|retrieval]] of specific items from a [[set (mathematics)|set]] of items, such as a specific [[record (computer science)|record]] from a [[database]].
The simplest, most general, and least efficient search structure is merely an unordered sequential [[list (computing)|list]] of all the items. Locating the desired item in such a list, by the [[linear search]] method, inevitably requires a number of operations proportional to the number ''n'' of items, in the [[worst case complexity|worst case]] as well as in the [[average case complexity|average case]]. Useful search data structures allow faster retrieval; however, they are limited to queries of some specific kind. Moreover, since the cost of building such structures is at least proportional to ''n'', they only pay off if several queries are to be performed on the same database (or on a database that changes little between queries).
'''Static''' search structures are designed for answering many [[Information retrieval|queries]] on a fixed database; '''dynamic''' structures also allow insertion, deletion, or [[Update (SQL)|modification]] of items between successive queries. In the dynamic case, one must also consider the cost of fixing the search structure to account for the changes in the database.
==Classification==
| |||