8

In databases like MySQL or Oracle, how are indexes implemented? I think regular indexes are stored as B-trees, but couldn't find anything about composite indexes that index on multiple columns. I'm looking for the names of the data structures used so I can research them.

More generally, where can I find more such information about database implementation details? I'm going to be taking a course on that much later in university, but I'm curious right now.

2 Answers 2

7

Composite indexes also use B-Trees, they just concatenate the indexed columns to determine the key. As a side node, Oracle also knows other index types, i.e. bitmap indexes. But that doesn't depend on the number of columns indexed.

4

B-trees. Every index is stored as a B-tree -- even composite ones.

If you're looking to do more research on how indexes are organized, look into B+ trees and B* trees. For SQL Server, Kalen Delaney's Inside SQL Server: The Storage Engine is an excellent book about the nuts and bolts of SQL Server, including its index organization. So you should definitely check that out.

A commenter points out that Oracle can use bitmap indexes, which are structured very differently than B-trees, but those are rarely used for traditional relational databases -- they're used more often for OLAP type applications and in cases where you need fast access on a nonselective group of data.

EDIT: SQL Server, for example, now uses Columnstore Indexes. If you do any work with large BI type workloads, it's definitely worth looking at these, as they store your data in an entirely different way than a B-Tree.

SQL Server also uses a different mechanism now for memory optimized tables as well, and is something that's very useful for OLTP type queries.

2
  • Except for ones that aren't - like bitmap indexes in Oracle.
    – David M
    Jul 15, 2009 at 12:23
  • I really did not understand why this answer got a downvote. The provided book reference was pretty helpful and it generally made the same point as the accepted answer. Jun 7, 2012 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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