1

As a theoretical database question, if you are asked 'which indexes would you propose and why?' are the answers from primary, clustering and secondary index? How would we know if we should introduce one of those vs a B-Tree?

This should be from a simplistic indexing perspective, as I am asking due to course material related to indexes, where I have covered some introductory material.

Improve this question

1 Answer 1

Reset to default
2

primary and secondary indices are orthogonal to b-tree and hash indices, and both of these are orthogonal to clustered and non-clustered indices.

  • The first class of indices are logical indices. They are high-level indicators about the structure of your data. The primary key should uniquely identify your data, which means it should be one of what relation database theory calls a "candidate key". Secondary indices are for speeding up queries against other fields than the main index and they do not need to be candidate keys.

  • The second class are specific index implementations, fit for slightly different queries. b-tree can fulfill range queries (WHERE c > 3 AND c < 7) which hash cannot. hash is however O(1) (constant time) in the average case on exact queries (WHERE c = 5), while b-tree is O(lg n) (logarithmic time) always. b-tree and hash are both well-defined datastructures, but they have very little to do with your actual data.

  • The third class defines if the entire table is sorted on disk by the sorting order of the index. If that's the case it's called a clustered index.

As you can see an index can be a primary clustered b-tree or a primary clustered hash or some other combination drawn from these three different classes.

If you were asked which indices to introduce, the answer would foremost be from the first class. The question is probably about the schema. That's your starting point at least. Only when you have decided what indices to introduce do you need to think about whether they should be b-trees, clustered etc. The first class is a logical one, tightly coupled with how you are using the data. The others are implementation details.

Improve this answer
2
  • I'll add my 2 cents - b-tree search complexity is O(log n) for both search and insert, not O(n log n), hash search complexity is O(1) for insert and O(n) for worst case in search. Since there's 'mysql' tag in question, in mysql primary index is always clustered.
    – DukeLion
    Jun 7, 2012 at 10:32
  • DukeLion, you are of course correct. I've clarified the time-complexities somewhat and removed my typo on lg n. Also, in MySQL the MyISAM and InnoDB storage engines don't support hash indices. B-tree should perform almost equally well because the trees are usually very shallow in depth due to the large amount of children in each node.
    – Emil Vikström
    Jun 7, 2012 at 11:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .