创建高性能的索引 | 索引的类型

04
六月
2021

目录

介绍

索引基础---索引的类型

B-Tree索引

哈希索引

空间数据索引

全文索引

其他类型的索引


介绍

索引是一种存在于数据库字段的,用于提高查询效率的机制。简单的说,索引相当于一本书的目录,帮助读者快速的定位到目标内容。

良好的索引的设计可以大大提高查询性能,尤其当表中的数据量越来越大时,索引对性能的影响愈发的重要。面对日益增长的数据,立足索引的优化是提升性能最好的手段了,它对应用的改变是数量级的。

尽管为查询中使用的每个可能的列创建索引可能很诱人,但不必要的索引浪费了 MySQL 确定使用哪些索引的空间和时间。索引还会增加插入、更新和删除的成本,因为每个索引都必须更新。必须找到正确的平衡点,才能使用最佳索引集实现快速查询。所以索引知识是研发人员的必备技能。


索引基础---索引的类型

索引有很多种类型,可以为不同的场景提供更好的性能。在MySQL中,索引是在存储引擎层而不是服务器层实现的。所以,并没有统一的索引标准;不同的存储引擎的索引工作方式并不一样。

下面介绍MySQL支持的索引类型,及优缺点。

B-Tree索引

此处为广义B-Tree,包含btree和b+tree(b plus树)。基于B树衍生出的全部类型如下:

B-Tree索引使用B-Tree数据结构来存储数据。大多数MySQL引擎都支持这种索引。B-Tree通常意味着所有的值都是按顺序存储的。并且每一个叶子页到根的距离相同。

B-Tree索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫面来吼去需要的数据,取而代之的是从索引的根节点开始进行搜索。

可以使用B-Tree索引的查询类型。B-Tree索引使用于全键值、键值范围或键前缀查找。其中键前缀查找只适用于根据最左前缀的查找。具体对如下类型的查询有效:

  • 全值匹配 :全值匹配指的是和索引中的所有列进行匹配,例索引用于查找姓名为thump、出生于1900-01-01的人
  • 匹配最左前缀:查找所有姓为Allen的人,即只使用索引的第一列
  • 匹配列前缀:也可以只匹配某一列的值的开头部分,例如索引可用于查找所有J开头的姓的人,这里只使用了索引的第一列。
  • 匹配范围值:查找行姓名再Allen和Jack的人,这里也只使用了索引的第一列。
  • 精确匹配某一列并范围匹配另一列:查找姓为Allen,并且名字为字母K开头的人,即第一列last_name全匹配,第二列first_name范围匹配。
  • 只访问索引的查询:B-Tree通常可以支持“只访问索引的查询”,即查询只需要访问索引,而无需访问数据行。

关于B-Tree、B+Tree的详细知识可以参考面试官问你B树和B+树,就把这篇文章丢给他

哈希索引

哈希索引基于哈希表实现,只有精确匹配所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码,哈希码是一个较小的值,并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。

在MySQL中只有memory引擎支持哈希索引,其余引擎并不支持。

示例:

CREATE TABLE `testhash` ( `fname` varchar(50) DEFAULT NULL, `lname` varchar(50) DEFAULT NULL, KEY `fname` (`fname`) USING HASH) ENGINE=MEMORY;

INSERT INTO `testhash` VALUES ('Trump', '川建国');
INSERT INTO `testhash` VALUES ('jack', '杰克');
INSERT INTO `testhash` VALUES ('lucy', '露西');
INSERT INTO `testhash` VALUES ('lili', '丽丽');

假设索引使用哈希函数f()来生成哈希码:

f('Trump')=2323  f('jack')=7437  f('lucy')=8784  f('lili')=2458

则,哈希索引的数据结构是:

看如下查询:

select lname from testhash where fname ='lucy'

Mysql首先计算Peter的哈希值是8784,然后到哈希索引中找到对应的行指针,根据指针找到对应的数据行。

索引只存储哈希码及行指针,所以索引的数据结构非常的紧凑,这也让哈希索引查找速度非常快,但是哈希索引也有他的限制。

哈希索引的局限性

  • 哈希索引基于哈希表实现,只有精确匹配所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码,哈希码是一个较小的值,并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。
  • 哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。不过,访问内存中的行的速度很快,所以大部分情况下这一点对性能的影响并不明显。
  • 哈希索引数据并不是按照索引值顺序存储的,所以也就无法用于排序。
  • 哈希索引不支持部分索引列匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如,在数据列(A,B)上建立哈希索引,如果查询只有数据列A,则无法使用该索引。
  • 哈希索引只支持等值比较查询,包括=、IN()、<=>。也不支持任务范围查询,例如WHERE price >100。
  • 访问哈希索引的数据非常快,除非有很多哈希冲突。当出现哈希冲突的时候,存储引擎必须遍历链表中所有的行指针,逐行进行比较,知道找到所有符合条件的行。
  • 如果哈希冲突很多的话,一些索引维护操作的代价也会很高。例如如果在某个选择性很低的列上建立哈希索引,那么当总表中删除一行时,存储引擎需要遍历对应哈希值的链表中的每一行,找到并删除对应行的引用,冲突越多,代价越大。

哈希索引的应用场景

还真没用过hash索引,不过基于它的的特性来看,它适用于一些全值比较的场景,例如网站的ip 黑名单表。欢迎实战过的朋友评论区补充适用场景。

InnoDB引擎有个特殊的功能叫做“自适应哈希索引(adaptive hash index)”。当InnoDB注意到某些索引值被使用的非常频繁时,它会在内存中基于B-Tree索引之上再创建一个哈希索引,这样就让B-Tree索引也具有哈希索引的一些优点,比如快速的哈希查找。这是一个完全自动、内部的行为,用户无法控制。如果有必要用户可以关闭该功能。

如果存储引擎不支持hash索引,可以像InnoDB模拟哈希索引,可以享受一些哈希索引的便利。在数据入库时转为hash值,查找时手动指定hash函数。

空间数据索引

MyISAM表支持空间索引,可以用作地理数据存储。和B-Tree索引不同,这类索引无需前缀查询。空间索引会从所有维度来索引数据。查询时,可以有效的使用任意维度来组合查询。必须使用MySQL的GIS相关的函数如MBRCONTAINS()等来维护数据。MySQL的GIS支持并不完善,大部分人不会使用这个特性。

全文索引

全文索引是一种特殊类型的索引,它查找的是文本中的关键词,而不是直接比较索引汇总的值。全文搜索和其他几类索引的匹配方式完全不一样。它有许多需要注意的细节,如停用词、词干和复数、布尔搜索等。全文索引更类似搜索引擎干的事情,而不是简单的WHERE条件匹配。

这玩意不错啊,遥想起做电商的时候,自己搭solr,配规则、维护数据、优化索引,忙活了好久,检索效果还不咋地。而且后来用户量也没起来,solr大材小用了。当初要是知道全文索引的话,说不定可以先用这玩意顶一阵子。看来还得多学习啊,能少走弯路。

简单使用方式如下:

---建表
create table fulltext_test (
    id int(11) NOT NULL AUTO_INCREMENT,
    content text NOT NULL,
    tag varchar(255),
    PRIMARY KEY (id),
    FULLTEXT KEY content_tag_fulltext(content,tag)  
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
---自己写入数据

---查询 和常用的模糊匹配使用 like + % 不同,全文索引有自己的语法格式,使用 match 和 against 关键字

SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('清华' IN NATURAL LANGUAGE MODE);

SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('清华');

全文索引可以设置停词、分词等,

其他类型的索引

还有很多第三方的存储引擎使用不同类型的数据结构来存储索引。例如TokuDB使用分形树索引,这是一类较新开发的数据结构,既有B-Tree的很多优点,也避免B-Tree的一些缺点。ScaleDB使用 Partricia tries,其他一些存储引擎技术如InfiniDB和Onfobright使用了一些特殊的数据结构来优化某些特殊的查询。 


参考:

《高性能MySQL》

面试官问你B树和B+树,就把这篇文章丢给他

Mysql使用全文索引(FullText index)

MySQL 之全文索引

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员