MySQL索引及其实现原理(基于MyISAM及InnoDB引擎)
bTreeSearch(node, key) {
if(node == null) return null;
foreach(node.key) {
if(node.key[i] == key) return node.data[i];
if(node.key[i] > key) return bTreeSearch(point[i]->node);
}
return bTreeSearch(point[i+1]->node);
}
data = bTreeSearch(root, my_key);
2. MySQL索引实现
在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式
2.1 MyISAM索引实现
MyISAM引擎使用B+Tree作为索引结构,叶节点data域存放数据记录的地址
图8 MyISAM索引的原理图
设Col1为主键,则图8是一个MyISAM表的主索引(Primary key)示例。
可以看出MyISAM的索引文件仅仅保存数据记录的地址。
在MyISAM中,主索引和辅索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅索引的key可以重复
如果我们在Col2上建立一个辅索引,则此索引的结构如下图所示:
图9
同样也是一颗B+Tree,data域保存数据记录的地址。
因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分
2.2 InnoDB索引实现
虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同
第一个重大区别是InnoDB的数据文件本身就是索引文件。
从上文知
- MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址
- 而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引
图10 InnoDB主索引(同时也是数据文件)的示意图
可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。
因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形
第二个与MyISAM索引的不同是InnoDB的辅索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,
图11 定义在Col3上的一个辅索引
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,
例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅索引都引用主索引,过长的主索引会令辅索引变得过大。
再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择
下一章将具体讨论这些与索引有关的优化策略
3. 索引使用策略及优化
3.1 索引的好处
3.2 什么情况下可以用到B树索引
(1) 定义有主键的列一定要建立索引。因为主键可以加速定位到表中的某行
(2) 定义有外键的列一定要建立索引。外键列通常用于表与表之间的连接,在其上创建索引可以加快表间的连接
(3) 对于经常查询的数据列最好建立索引。
① 对于需要在指定范围内快速或频繁查询的数据列,因为索引已经排序,其指定的范围是连续的,查询可以利用索引的排序,加快查询的时间
② 经常用在 where子句中的数据列,将索引建立在where子句的集合过程中,对于需要加速或频繁检索的数据列,可以让这些经常参与查询的数据列按照索引的排序进行查询,加快查询的时间
MySQL的优化主要分为
结构优化(Scheme optimization)
查询优化(Query optimization)
本章讨论的高性能索引策略主要属于结构优化范畴