range query
A request for every item whose key lies between two bounds, such as all orders placed between 9:00 and 10:00.
In more detail
Range queries need sorted order: on a sorted list, two binary searches find the bounds in O(log n) and the results sit between them. A hash table has no notion of "between" and must scan all n items. Database indexes use B-trees largely for this reason.
Related terms
- sorted list — A list kept in ascending order, which supports O(log n) search with binary search at the cost of O(n) insertion.
- bisect module — Python's standard-library module of correct binary-search functions for sorted lists.
- B-tree — A balanced search tree whose nodes each hold many sorted keys and have many children, so the tree is very wide and very shallow.
- hash table — A data structure that stores key-value pairs in an array and uses a hash of each key to jump almost directly to its slot.
Taught in
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers