Benefits of BTREE in MySQL

Question

What are the pros and cons of using a BTREE index in MySQL, regarding query speed, disk storage and memory usage?

• Does BTREE provide easier iteration in increasing order ?
• What kind of queries would benefit from a BTREE ?
• Are there any disadvantages of using BTREE index ?
• Does it increase space or indexing time?

Answer 1

Regardless of the Storage Engine (MyISAM or InnoDB), when it comes to BTREEs, you must make sure you understand the following characteristics:

• Keys should be as small as possible
• Random Keys for PRIMARY KEYs
  • Insertions (Bulk or Programmatic) will perform root node and internal splitting periodically
  • Introduces Overhead early in an index's life
  • Breeds node fragmentation (especially for index pages)
  • Causes Index Scans for Queries to be performed Randomly
• Ordered Keys for PRIMARY KEYs
  • Bulk Ordered Insertions delay root node and internal splitting
  • Reloading data via mysqldump files and LOAD DATA INFILE commands promote the use of sorting mechanisms to address index initialization/reorganization (See my Oct 26, 2012 post: How badly does innodb fragment in the face of somewhat out-of-order insertions?)
  • Programmatic Ordered Insertions promote root node and internal splitting of index pages in 45% of the cases
  • Delays creation of Overhead
  • Prevents node fragmentation
  • Causes Index Scans for Queries to be performed Sequentially (less disk I/O)

When it comes to BTREEs in InnoDB, they tend to be more bloated than that of its counterparts MyISAM because of InnoDB's gen_clust_index, where row data live.

The PRIMARY KEY of an InnoDB table points right to its gen_clust_index. Secondary indexes always include a PRIMARY KEY entry. If you run a query that uses a Secondary Index and also has non-indexed columns in the WHERE clause, you could easily be doing two Index Lookups. With that in mind, you need to make sure all Secondary Indexes have all the needed columns for you queries' WHERE clauses (a.k.a. Covering Index).

Answer 2

Pros and cons compared to what? From the documentation:

index_type

Some storage engines permit you to specify an index type when creating an index. The permissible index type values supported by different storage engines are shown in the following table. Where multiple index types are listed, the first one is the default when no index type specifier is given.

Storage Engine   Permissible Index Types
----------------------------------------
MyISAM           BTREE
InnoDB           BTREE
MEMORY/HEAP      HASH, BTREE
NDB              HASH, BTREE

The index_type clause cannot be used together with SPATIAL INDEX.

Answer 3

I don't think there is too much specific to Mysql regarding B-tree indexes.
Main idea of B-tree index is to minimize the number of physical reads. Since the data structure is sorted, B-tree index can be used effectively for range scans . Seeks are not so effective compared to hash indexes. Deletes cause fragmentation, sequential inserts are relative cheep, non-sequential inserts and updates may be very expensive; however, modern RDMS usually handle them with decent performance.

Answer 4

looking at the benefit purely from the underlying data structures.

1. HASH type index will be more time efficient but less space efficient
2. BTREE type index will be more space efficient but less time efficient