MySQL Indexing Mechanism

BTree (in fact B*Tree) is an efficient ordered key-value map. that means that a BTREE index can quickly find a record given the key, and it can be scanned in order. It also makes easy to fetch all keys (and records) within a range: "all events between 9am and 5pm", "last names starting with 'R'"

RTREE is an 'spatial index' that means that it can quickly identify 'close' values in 2 or more dimentions. Used in geographic databases for queries like "all points within X meters from (x,y)"

HASH is an unordered key-value map. It's even more efficient than BTREE: O(1) instead of O(log n); but it doesn't have any concept of order. That means that is can't be used to avoid sort operations, or to fetch ranges. 

Originally, MySQL only allowed HASH indexes on MEMORY tables; but i'm not sure if that has been relaxed. 

http://www.informit.com/articles/article.aspx?p=377652