Adaptability and limitations of MySQL B-Tree indexes

By:    Updated: February 28,2017

Storage engines use B-Tree indexes in various ways, which can affect performance. For instance, MyISAM indexes refer to the indexed rows by their physical storage locations, but InnoDB refers to them by their primary key values. Each variation has benefits and drawbacks.

 

A B-Tree index speeds up data access because the storage engine doesn't have to scan the whole table to find the desired data. Instead, it starts at the root node. The slots in the root node hold pointers to child nodes, and the storage engine follows these pointers. It finds the right pointer by looking at the values in the node pages, which define the upper and lower bounds of the values in the child nodes. Eventually, the storage engine either determines that the desired value doesn't exist or successfully reaches a leaf page.

Adaptability of B-Tree indexes

B-Tree indexes work well for lookups by the full key value, a key range, or a key prefix. They are useful only if the lookup uses a leftmost prefix of the index.

create table if not exists vv_members 
(
  id int(11) unsigned not null auto_increment primary key,
  first_name varchar(32) not null default '',
  last_name varchar(32) not null default '',
  birthday date not null default '2000-01-01',
  add_time int(11) unsigned not null default 0,
  key(last_name, first_name, birthday)
)engine=innodb default charset=utf8

insert into vv_members(first_name,last_name,birthday,add_time)  values 
('Flasle','Cheng','2017-02-28',1488282959), 
('Ariel','Liu','2017-02-28',1488282959)
  • Match the full value: A match on the full key value specifies values for all columns in the index. For example, this index can find a member named Flasle Cheng who was born on 2017-02-28.
  • Match a leftmost prefix: This index can find all members with the last name Cheng. This uses only the first column in the index.
  • Match a column prefix: Match on the first part of a column's value. This index can find all people whose last names begin with C. This uses only the first column in the index.
  • Match a range of values: This index can find people whose last names are between Cheng and Liu. This also uses only the first column. Because B-Trees store the indexed columns in order, they're useful for searching for ranges of data.
  • Match one part exactly and match a range on another part: This index can find everyone whose last name is Cheng and whose first name starts with the letter F (Flasle, Flash, etc.). This is an exact match on last_name and a range query on first_name.
  • Index-only queries: B-Tree indexes can normally support index-only queries, which are queries that access only the index, not the row storage.

Limitations of B-Tree indexes

  • They are not useful if the lookup does not start from the leftmost side of the indexed columns. For example, this index won't find all members with first name Flasle or born on a certain date, because those columns are not leftmost in the index. Likewise, you can't use the index to find members whose last name ends with a particular letter.
  • You can't skip columns in the index. That is, you won't be able to find all members whose last name is Cheng and who were born on a particular date. If you don't specify a value for the first_name column, MySQL can use only the first column of the index.
  • The storage engine can't optimize accesses with any columns to the right of the first range condition. For example, if your query is where last_name='Cheng' and first_name like 'F%' and birthday='2017-02-28', the index access will use only the first two columns in the index, because the like is a range condition. For a column that has a limited number of values, you can often work around this by specifying equality conditions instead of range conditions.
More in Development Center
New on Valinv
Related Articles
Sponsored Links