Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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?
share|improve this question
    
Pros and cons compared to what exactly? –  ypercube Jun 28 '12 at 8:50
    
Added details, thanks. –  Adam Matan Jun 28 '12 at 10:15
    
BTREE is your only option with MySQL unless you are using MEMORY or NDB (MySQL Cluster) engines. –  Aaron Brown Jun 28 '12 at 21:24

4 Answers 4

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.

share|improve this answer
2  
Given that MyISAM and InnoDB do not support any other type, the only valid comparison is between BTREE index and no index at all ... –  ypercube Jun 27 '12 at 16:28
    
@ypercube - I'm curious whether the OP meant this. –  dezso Jun 27 '12 at 16:57

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.

share|improve this answer

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
share|improve this answer
    
Can you expand on this at all? –  Jon of All Trades Jun 28 '12 at 17:23
2  
Your statement is only correct for constant lookups and is false for range lookups. –  Aaron Brown Jun 28 '12 at 21:24

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

  • Keys should 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 pages0
    • 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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.