What are the actual types of database indexes?


I've been searching on the net for the types of database indexes, but I haven't found a real answer. Most of the pages say that there are two types (Clustered and Non-Clustered) but some others say different terms like (Simple, composite, B-tree, Bitmap, unique, non-unique, FBI, Dense, Sparse, Reverse, ...etc).

I know its different between DBMSs but why most of the sources there are just two types (Clustered and Non-Clustered)? What are types of indexes supported by SQL?

Can someone give me more explanation?

Answer

This is not a simple reply. I try to explain the topic in some paragraph and I'll speak about SQL Server, as a RDBMS..

When we speak about Clustered/Nonclustered and heaps (hobt --> heaps or b-tree) we're indicating "structures" in which objects (tables or indexed views) are stored. Indeed, heaps are simple "list" of items, stored without any particular order; clustered are structures which "organize" row data in trees (called b+tree) sorted by the index key and they are the objects themselves (a table can be a heap or a clustered structure); nonclustered are similar to the clustered structures, but they don't represent the tables (nor indexed views). They're additional structures which point to the clustered or heap underlying object.

Recap

A table (or an indexed view) can be stored in heaps or clustered (SQL Server can have just one clustered structure). A table (or an indexed view) can have more than one additional structures as nonclustered index in order to have more than one kind of accessing data. Every nonclustered index will point to the heap or to the clustered underlying object, depending on how the data are organized (it depends on whether you've created a clustered or not)

That said, we can say that non heap structures can support various kind of index:

  • simple/composite implementations: clustered or nonclustered, just indexes with a key, which is a single column key or a set of columns.
  • unique index: clustered or nonclustered, it supports just one value per row (on the key of the index). It's related to a "unique constraint" or "primary key constraint" which guarantee the uniqueness of the values. The difference between unique and pk is that pk does not accept NULL values.
  • covering index: just nonclustered, because the clustered structure has the record inside it. It's an index with a set of columns included (INCLUDE clause) in the leaf (remember, it's a tree). It's called covering index because it is an index which covers a certain query, without looking up on the underlying object.
  • filtered index: just nonclustered, because you cannot filter out part of the table which is stored as a clustered structure. It's an index with a WHERE clause, which considers just a portion of the underlying objects. The condition must be deterministic (for example, you cannot use WHERE StartDate >= GETDATE()).

The indexes above are the most used (in my experience) but we can add also:

  • Indexes on computed columns
  • Spatial indexes
  • XML indexes
  • Full-text indexes
  • Columnstore indexes (starting from 2012)
  • Memory optimized indexes (starting from 2014)

Finally you can have also a set of concepts about indexes, which are not type of indexes, but you can hear about them:

  • overlapped indexes
  • duplicated indexes
  • missing indexes
  • unused idexes

Hope this helps.

source: stackoverflow.com
js interview questions