Indexes

From BaseX Documentation
Revision as of 16:58, 13 December 2010 by Michael (talk | contribs) (→‎Full-Text Index: added link)
Jump to navigation Jump to search

Existing Indexes

Indexes can speedup queries by magnitudes. Currently, four indexes exist:

Text Index
This index speeds up text comparisons in predicates.
Attribute Index
This index speeds up attribute value comparisons in predicates.
Full-Text Index
Full-text queries are sped up by this index.
Path Summary
This index speeds up the resolution of location paths.

Examples of using the indexes

Here are some examples for queries which are rewritten for index access:

Text-Based Queries

  • //node()[text() = 'Usability']
  • //div[p = 'Usability' or p = 'Testing']
  • path/to/relevant[text() = 'Usability Testing']/and/so/on

Attribute Index

  • //node()[@align = 'right']
  • descendant::elem[@id = '1']
  • range/query[@id >= 1 and @id <= 5]

Full-Text Index

  • //node[text() contains text 'Usability']
  • //node[text() contains text 'Usebiliti' using fuzzy]
  • //book[chapter contains text ('web' ftor 'WWW' using no stemming) ftand 'diversity' using stemming distance at most 5 words]

The full-text index is optimized to support all features of the XQuery Full Text Recommendation.

BaseX extends the specification by offering a fuzzy match option. Fuzzy search is based on the Levenshtein algorithm; the longer query terms are, the more errors will be tolerated.

Default "Case Sensitivity", "Stemming" and "Diacritics" options will be considered in the index creation. Consequently, all queries will be sped up which use the default index options.

Index data structures

Text/Attribute Index
Both the text and attribute index are based on a balanced B-Tree and support exact matches and range queries.
Full-Text Index (Standard)
The standard full-text index is implemented as sorted array structure. It is optimized for simple and fuzzy searches.
Full-Text Index (Wildcards enabled)
A second full-text index is implemented as a compressed trie. Its needs slightly more memory than the standard full-text index, but it supports more features, such as full wildcard search.