Search data structure: Difference between revisions

Revision as of 19:34, 12 January 2010

Revision as of 03:11, 14 January 2010

Line 1:

In [[computer science]], a '''search data structure''' is any [[data structure]] that allows the efficient 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 strcuturestructure 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 [[queries]] on a fixed database; '''dynamic''' structures also allow insertion, deletion, or 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.