Search data structure: Difference between revisions

Revision as of 04:02, 3 January 2010

Revision as of 19:34, 12 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 (computingcomputer science)|record]] from a [[database]].

The simplest, most general, and least efficient search strcuture 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).