{notes} very very good article
Excerpt:: please see the original one for details.
Hashes can deal with equality but not inequality. That is, given the hashes of two fields, there's just no way for me to tell which is greater than the other, only whether they're equal or not.
B-tree Indexes
The data structure most commonly used for database indexes are B-trees, a specific kind of self-balancing tree.
The main benefit of a B-tree is that it allows logarithmic selections, insertions, and deletions in the worst case scenario. And unlike hash indexes it stores the data in an ordered way, allowing for faster row retrieval when the selection conditions include things like inequalities or prefixes.For example, using the tree above, to get the records for all people younger than 13 requires looking at only the left branch of the tree root.
Other Indexes
Hash indexes and B-tree indexes are the most common types of database indexes, but there are others, too. MySQL supports R-tree indexes, which are used to query spatial data, e.g., "Show me all cities within ten miles of San Francisco, CA." There are also bitmap indexes, which allow for almost instantaneous read operations but are expensive to change and take up a lot of space. They are best for columns which have only a few possible values.
The penalty for having a database index is the cost required to update the index, which must happen any time the table is altered. There is also a certain about of space overhead, although indexes will be smaller than the table they index. For specific data types different indexes might be better suited than a B-tree. R-trees, for example, allow for quicker retrieval of spatial data. For fields with only a few possible values bitmap indexes might be appropriate.
No comments:
Post a Comment