What is the difference between btree and rtree indexing?

Question

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

BTREE
RTREE
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?)

score 70 · Accepted Answer · edited Jul 22 '19 at 15:34

70

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.

edited Jul 22 '19 at 15:34

Can Sürmeli

103
4

answered Oct 09 '11 at 12:51

Javier

9,888
1
26
35

Does MySQL support Rtrees? – Pacerier Jul 05 '12 at 23:14
4

yes, they're called SPATIAL INDEX (http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html) – Javier Jul 05 '12 at 23:37
Cool, thanks =) Are there other structures besides these 3, or planned structures in the near future? – Pacerier Jul 06 '12 at 03:40
Memory tables support btree indexes as well – Amareswar Oct 20 '12 at 20:11
1

@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

Ham · Answer 2 · 2021-06-22T15:11:42.837

The accepted answer contains good quality of information. index type selection is limited by the storage engine applied to the database table, here is extra information about the index types supported by the storage engines in MySQL. See Table 16.1 Storage Engines Feature Summary in Alternative Storage Engines in MySQL 8.0 documentation

In short , here are the storage engines that support these 3 index types.

B-tree index : MyISAM, Memory, InnoDB
Hash index : Memory
R-tree (Geospatial) index: MyISAM , InnoDB(since MySQL 5.7)

side note:

InnoDB internally utilizes hash indexes.
This also describes difference between B-tree and hash index in term of usage limit at application level

What is the difference between btree and rtree indexing?

2 Answers2

BTree

RTree

Hash