首页 > 数据库 > MySQL索引介绍

MySQL索引介绍

2016年4月20日 963 views 发表评论 阅读评论

目前MySQL主要支持的几种索引:B树索引(B-tree),哈希索引( hash) ,空间索引Spacial(R-tree),全文索引(full-text)

B树索引介绍

实际MySQL实现的B+树,它的索引如下图(摘录自high performance MySQL )

1

以上是一个简单的图,包括了一个节点块,块内包含一定数量的键值(如key1…keyn) 以及它的叶块(leaf pages),页块内的所有值(Val…)按大小顺序排列,各页块用指针进行连接。

实际的系统,根(root)节点到叶块之间可能有多层的节点块(node page),树的深度取决于表的大小.假设一个块内能存放256个元素,那么3层的树可以存储>1千万的元素.由于有这样的一个层次结构,往往经过2、3次的索引查找,就可以定位到记录,可以大大减少磁盘的读取次数。各页块之间有指针连接,那么还可以方便的进行顺序范围查找。

参考:http://zh.wikipedia.org/wiki/B%2B%E6%A0%91

 

估计查询性能

对小的表,通常能在1次磁盘搜索中找到行(因为索引可能被缓存)。对更大的表,可以使用B-树索引进行估计,将需要log(row_count)/log(index_block_length/3 * 2/(index_length + data_pointer_length))+1次搜索才能找到行。

 

在MySQL中,索引块通常是1024个字节,数据指针通常是4个字节,这对于有一个长度为3(中等整数)的索引的500,000行的表,通过公式可以计算出log(500,000)/log(1024/3*2/(3+4))+1= 4次搜索。

 

上面的索引需要大约500,000 * 7 * 3/2 = 5.2MB,(假设典型情况下索引缓存区填充率为2/3),可以将大部分索引保存在内存中,仅需要1、2次调用从OS读数据来找到记录。

 

然而对于写,将需要4次搜索请求(如上)来找到在哪儿存放新索引,并且通常需要2次搜索来更新这个索引并且写入行。

 

注意,上述讨论并不意味着应用程序的性能将缓慢地以logN 退化!当表格变得更大时,所有内容缓存到OS或SQL服务器后,将仅仅或多或少地更慢。在数据变得太大不能缓存后,将逐渐变得更慢,直到应用程序只能进行磁盘搜索(以logN增加)。为了避免这个问题,应随数据增加而增加innodb_buffer_pool的大小。尽量缓存大部分索引和热点数据。

 

 

哈希索引(hash indexes)

哈希索引是通过构建哈希数组(表) ,通过对值进行hash,查找hash表, 找到真实的行记录的(hash表存储了行记录的指针)。

哈希索引目前只在memory storage engine中支持,也是它的默认索引类型。这是一个不常用的功能。如需了解,可参考

http://dev.MySQL.com/doc/refman/5.1/zh/storage-engines.html

 

空间索引(spacial indexes)

目前在myisam engine中支持. 如需了解,请参考

http://dev.MySQL.com/doc/refman/5.1/zh/spatial-extensions-in-MySQL.html#creating-spatial-indexes

 

 

全文索引(full-text indexes)

全文索引)在myisam engine中支持,如果是其他引擎,一般需要采用第三方的方案,如sphinx,Lucene, Solr等(有个好消息,MySQL 5.6 InnoDB开始支持全文索引了). MySQL在大数据量下的全文索引性能不佳,且无法支持正确的支持中文,一般中文的解决方案,建议采用第三方的解决方案,可参考sphinx等全文索引方案,sphinx可实现快速,高效,可扩展的全文搜索,其性能大大超过MySQL内建的全文搜索

 

一般如果没有特别指明,就是B-Tree索引.由于索引是在存储引擎层实现的,不同的存储引擎的索引实现会有一些差异,以下所述是一些较通用的索引的知识.

逻辑上可以分为:单列索引,复合索引(多列索引),唯一索引(unique),非唯一索引(Non Unique)

 

索引键值的逻辑顺序与索引所服务的表中相应行的物理顺序相同的索引,被称为聚集索引(cluster index),也就是说数据和索引(B+树)在一起,记录是真实的保存在索引的叶子中。有些人也称之为索引组织表,反之为非聚集索引。我们常用的InnoDB表其实就是使用的聚集索引。

聚集索引是一个很重要的概念,InnoDB作为我们最常使用的引擎,我们熟悉了它的数据存储方式,才可能有针对性的对它进行调优。

簇索引的一些优点:

保持相关的的数据在一起,叶子内可保存相邻近的记录。

查找数据通常比非簇索引更快,因为索引和数据存储在一起。

如果充分利用以上,簇索引可极大提升性能, 但簇索引也有许多不足:

簇索引对i/o密集型负荷性能提升最佳,但如果数据是在内存中(访问次序不怎么重要),那么簇索引并没有明显益处;

插入操作很依赖于插入的次序,按primary key的顺序插入是最快的;

更新簇索引列的成本比较高,因为InnoDB不得不移动更新的行到新的位置;

全表扫描的性能差,尤其是行存储的不那么紧密,或者因为页分裂(page split)而存储不连续;

二级索引的叶节点中存储了主键索引的值,如果主键采用得是较长的字符,那么索引可能很大,且通过二级索引查找数据也需要两次索引查找;

 

以下图(来自high performance MySQL 3rd)很好的说明了MYisam和InnoDB的怎样排列我们的表数据。我们对比下InnoDB和MyISAM的数据分布.

2

如上的索引是B+树,各存储引擎大致类似,一颗二叉树,从根节点出发,各子节点指向更深层的子节点或者叶子节点。

我们对比下主键索引和二级索引

InnoDB

主键是一个B树的结构,数据是按照主键(primary key)的顺序来存储的,由于主键是有序的,很显然,对于InnoDB表,最高效的存取方式是按主键取唯一记录或者小范围的主键扫描。如果是其他二级索引(secondary key), 那么也是一个B树的的结构,但是它的leaf page (leaf nodes)存储的不是实际数据指针而是主键的值(key+PKcols). 如果按照二级索引去检索记录,会需要通过存储的主键值再去查找记录,即多了一层join ,这样的好处是当行移动或者页分裂的时候,不用维护二级索引. 当然,如果主键占据过多字节,那么会造成二级索引存储开销也大. 所以强烈建议主键使用整型,以减少二级索引的存储开销。

myisam

按照插入的顺序存储数据记录于磁盘;在其上构建的主键索引和其他索引的结构并无不同.

这种结构是许多数据库采用的存储方式,数据和索引是分离的。主键索引是有序的,但按照主键索引做范围查找,实际指向的数据是没有顺序的,意味着随机读。MyISAM在现实互联网公司的生产环境中用得很少,这里不做过多介绍,仅仅因为文件容易损坏,就可以考虑否决它了。MyISAM仍然应用广泛,只是因为许多软件把它设为默认的引擎,且方便普通用户使用。

 

以上介绍了几种常用的索引以及InnoDB的数据存储方式。索引是在存储引擎中实现的,而不是MySQL server级, 但基本的索引类型原理大致类似。接下来我们介绍索引的一些规则,以及如何使用工具确认用到了合适的索引。

 

 » 转载保留版权:老陈 » 《MySQL索引介绍》
 » 如果喜欢可以: 点此订阅本站
分类: 数据库 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.