-1
  • Are there other ways of indexing?,
  • Which are the more used?
  • Does sql have an standard for indexes, it uses hash tables?

closed as too broad by Ixrec, gnat, Adam Zuckerman, Robert Harvey, Blrfl Apr 24 '16 at 12:11

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    Usually, the point of standards is to ensure the same behavior across all possible implementations. If you standardize the implementation, then you've completely missing the point. You can probably google the details on what each popular implementation is using. Various kinds of search trees are the most obvious alternative to hash tables. Also, "which are the best?" is far too broad for one question, as "the best" is obviously going to depend on the data and what you want to do with it. – Ixrec Apr 23 '16 at 16:50
  • 1
    It depends on the database. In MySQL, for example, the storage engines MyISAM and InnoDB use binary tree indexes while NDB and the in-memory engine also allow hashtables. See the documentation for details. – Philipp Apr 23 '16 at 17:25
  • 1
  • Folks, this is not stackoverflow - people are often referred to this forum for these type of questions. I thought of it as an interesting question fitting exactly this forum,is it not? – YoYo Apr 25 '16 at 3:33
3

Hash tables allow you to very quickly lookup an item if you have the exact key. Hash tables cannot handle a request like "give me all invoices issued from the 2nd to the 15th of April".

A lot of a time a database access wants all data in some range of values. Search trees work a lot better for that.

0

The ANSI SQL standard does not require hash indexes. Several relational database products have chosen hashing as an index implemention, however. PostgreSQL allows them to be explicitly declared. SQL Server uses hashing in its in-memory OLTP engine. Also, one way of implementing a SQL JOIN condition is to use hash tables, though these hash tables live only as long as the query is executing.

Index definition and use is a broad and on-going field of research. There are several variations on BTrees; bitmaps store one bit per row of interest and are most often used in datawarehouse scanarions; block and block range indexes store an index entry per disk block rather than per data row; indexes specific to natural language processing are common; fractal tree indexes aim to work around concurrency problems with BTrees; several others exist. Each of these has different characteristics for performance, concurrency, disk and memory, and the queries each can support.

The most commonly implemented index type is the B-Tree or one of its variants. As the name suggests, this is a tree-like structure. It stores one index entry per matching data row. The distance from root to leaf is the same length whatever path is chosen, and paths remains balanced after inserts and deletes (hence the name) which gives consistent performance across key ranges.

Not the answer you're looking for? Browse other questions tagged or ask your own question.