36

I've noticed on MySQLWorkbench that you can choose how to store your indexes before forward engineering your design. The storage types are:

  1. BTREE
  2. RTREE
  3. HASH

Researching this, I found some information that was pretty much over my head, so I'm looking for practical information on what the difference is between these and/or why you should choose one over another.

Also, I have never chosen a storage type before, so I assume MySQL is choosing a default storage type (BTREE?)

51

BTree

BTree (in fact B*Tree) is an efficient ordered key-value map. Meaning:

  • given the key, a BTree index can quickly find a record,
  • a BTree can be scanned in order.
  • it's also easy to fetch all the keys (and records) within a range.

e.g. "all events between 9am and 5pm", "last names starting with 'R'"

RTree

RTree is a spatial index which means that it can quickly identify close values in 2 or more dimensions. It's used in geographic databases for queries such as:

all points within X meters from (x,y)

Hash

Hash is an unordered key-value map. It's even more efficient than a BTree: O(1) instead of O(log n).

But it doesn't have any concept of order so it can't be used for sort operations or to fetch ranges.

As a side note, originally, MySQL only allowed Hash indexes on MEMORY tables; but I'm not sure if that has been changed over the years.

  • Does MySQL support Rtrees? – Pacerier Jul 5 '12 at 23:14
  • 2
    yes, they're called SPATIAL INDEX (dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html) – Javier Jul 5 '12 at 23:37
  • Cool, thanks =) Are there other structures besides these 3, or planned structures in the near future? – Pacerier Jul 6 '12 at 3:40
  • Memory tables support btree indexes as well – Amareswar Oct 20 '12 at 20:11
  • @Amareswar, right. Maybe my answer can be read both ways, but what i meant was that HASH indexes were only allowed on MEMORY tables, not on 'normal' tables. – Javier Oct 22 '12 at 14:05