Index Data Structure

An Index Data Structure is data structure that maps search keys to data record pointers.

• Context:
  • It can locate Data Records based on a partial information.
  • It can be the Output of an Indexing Task.
  • …
• Example(s):
  • an Array Data Structure.
  • an Associative Array, such as a hash table.
  • a Text Index Structure, such as a Lucene Index.
  • a Tree Index Data Structure, such as an R*-Tree.
  • a Database Table Index.
  • …
• Counter-Example(s):
  • a Data Record Set.
  • a Cache Data Structure.
• See: High-Dimensional Data Record Set, Document Index.

---

---

References

2018a

• (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Database_index Retrieved:2018-6-17.
  • A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure. Indexes are used to quickly locate data without having to search every row in a database table every time a database table is accessed. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random lookups and efficient access of ordered records.

    An index is a copy of selected columns of data from a table that can be searched very efficiently that also includes a low-level disk block address or direct link to the complete row of data it was copied from. Some databases extend the power of indexing by letting developers create indexes on functions or expressions. For example, an index could be created on upper(last_name), which would only store the upper case versions of the last_name field in the index. Another option sometimes supported is the use of partial indices, where index entries are created only for those records that satisfy some conditional expression. A further aspect of flexibility is to permit indexing on user-defined functions, as well as expressions formed from an assortment of built-in functions.

2018b

• (Python Tutorial, 2018) ⇒ https://docs.python.org/3/tutorial/datastructures.html Retrieved:2018-6-17.
  • QUOTE: list.index(x[, start[, end]])

    Return zero-based index in the list of the first item whose value is x. Raises a ValueError if there is no such item.

    The optional arguments start and end are interpreted as in the slice notation and are used to limit the search to a particular subsequence of the list. The returned index is computed relative to the beginning of the full sequence rather than the start argument.(...)

>>> fruits.index('banana')

3

>>> fruits.index('banana', 4) # Find next banana starting a position 4

6

2013

• (Savnik, 2013) ⇒ Iztok Savnik. (2013, September). "Index data structure for fast subset and superset queries". In: Proceedings of The International Conference on Availability, Reliability, and Security (pp. 134-148). Springer, Berlin, Heidelberg.
  • QUOTE: In this paper we propose a novel index data structure set-trie that implements efficiently basic two types of set containment queries: subset and superset queries. Set-trie provides storage for sets as well as multisets. Preliminary version of this paper has been published in [16].

     Set-trie is a tree data structure similar to trie [13]. The possibility to extend the performance of usual trie from membership operation to subset and superset operations comes from the fact that we are storing sets (multisets) and not the sequences of symbols as for ordinary tries. In case of sets (multisets) ordering of symbols in a set is not important as it is in the case of text. As it will be presented in the paper, the ordering of set elements is used as the basis for the definition of efficient algorithms for set containment operations. Since the semantics of set containment operations is equivalent to the semantics of multiset containment operations we will in the following text sometimes refer to both, sets and multisets, as sets.

2010

• (Milosavljevic et al., 2010) ⇒ Branko Milosavljevic, Danijela Boberic, Dušan Surla, (2010) "Retrieval of Bibliographic Records Using Apache Lucene". The Electronic Library, 28(4). doi:10.1108/02640471011065355
  • QUOTE:... A Lucene document may contain multiple fields with the same name and/or the same content. A Lucene index is a set of documents stored in a persistent storage (a file system, a database, etc.) supported by data structures providing for efficient retrieval. …

1996

• (Berchtold et al., 1996) ⇒ Stefan Berchtold, Daniel A. Keim, and Hans-Peter Kriegel. (1996). “The X-tree: An Index Structure for High-Dimensional Data.” In: Proceedings of VLDB Conference (VLDB 1996).
  • QUOTE:For querying these databases, it is essential to use appropriate indexing techniques which provide an efficient access to high-dimensional data. The goal of this paper is to demonstrate the limits of currently available index structures, and present a new index structure which considerably improves the performance in indexing high-dimensional data.

---