Search data structure (original) (raw)
In computer science, a search data structure is any data structure that allows the efficient retrieval of specific items from a set of items, such as a specific record from a database. The simplest, most general, and least efficient search structure is merely an unordered sequential 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 as well as in the 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 datab
| Property | Value |
|---|---|
| dbo:abstract | In computer science, a search data structure is any data structure that allows the efficient retrieval of specific items from a set of items, such as a specific record from a database. The simplest, most general, and least efficient search structure is merely an unordered sequential 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 as well as in the 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. (en) |
| dbo:wikiPageID | 24019691 (xsd:integer) |
| dbo:wikiPageLength | 8571 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121668041 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Queue_(abstract_data_type) dbr:List_of_data_structures dbr:Big-O_notation dbr:Information_retrieval dbr:Linear_search dbr:Longitude dbr:Stack_(abstract_data_type) dbr:Computer_science dbr:B-tree dbr:Trie dbr:Data_structure dbr:Heap_(data_structure) dbr:K-d_tree dbr:Linked_list dbr:Database dbr:Earth dbr:Record_(computer_science) dbr:Hash_table dbr:Array_data_structure dbr:Asymptotic_analysis dbr:AVL_tree dbr:Latitude dbr:Red–black_tree dbc:Data_structures dbr:Splay_tree dbr:Constant_time dbr:Cartesian_tree dbr:Set_(mathematics) dbr:Self-balancing_binary_search_tree dbr:Sorted_array dbr:Skip_list dbr:Average_case_complexity dbr:List_(computing) dbr:Worst_case_complexity dbr:Binary_search dbr:Dimension_(mathematics) |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Reflist |
| dct:subject | dbc:Data_structures |
| rdf:type | yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 yago:Structure105726345 yago:WikicatDataStructures |
| rdfs:comment | In computer science, a search data structure is any data structure that allows the efficient retrieval of specific items from a set of items, such as a specific record from a database. The simplest, most general, and least efficient search structure is merely an unordered sequential 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 as well as in the 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 datab (en) |
| rdfs:label | Search data structure (en) |
| owl:sameAs | yago-res:Search data structure wikidata:Search data structure dbpedia-sh:Search data structure dbpedia-sr:Search data structure https://global.dbpedia.org/id/4v45q |
| prov:wasDerivedFrom | wikipedia-en:Search_data_structure?oldid=1121668041&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Search_data_structure |
| is dbo:wikiPageRedirects of | dbr:Comparison_of_data_structures dbr:Search_data_structures |
| is dbo:wikiPageWikiLink of | dbr:Best,_worst_and_average_case dbr:Array_(data_type) dbr:Linear_search dbr:Heap_(data_structure) dbr:Hash_table dbr:Self-balancing_binary_search_tree dbr:Sorted_array dbr:Comparison_of_data_structures dbr:Search_data_structures |
| is rdfs:seeAlso of | dbr:Best,_worst_and_average_case |
| is foaf:primaryTopic of | wikipedia-en:Search_data_structure |