B-Tree索引与Hash索引的比较

标签: mysql index 索引 | 发表时间:2015-08-25 15:10 | 作者:FullStackDeveloper
出处:http://segmentfault.com/blogs

B-Tree索引与Hash索引的比较

翻译自 http://dev.mysql.com/doc/refman/5.6/en/index-btree-hash.html

理解B-Tree和Hash的数据结构能够帮助我们预测不同存储引擎下的查询性能差异。存储引擎在索引中使用这些数据结构,尤其是 MEMORY 同时提供了B-Tree和Hash索引让你选择。

B-Tree索引特性


B-Tree索引可以在表达式中使用=, >, >=, <, <=用作列比较或者 BETWEEN 运算符。还能使用LIKE比较,如果参数是一个不以通配符开头的常量。举个例子,下面的SELECT语句使用了索引:

  SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

第一条语句中,只有'Patrick' <= key col < 'Patricl' 的行会被考虑。第二条语句中,只有'Pat' <= keycol < 'Pau' 的行会被考虑。

下面的 SELECT语句没有使用索引:

  
SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE other_col;

第一条语句是因为它以通配符开头,第二条语句是因为没有使用常量。

如果你使用... LIKE '%string%'而且 string超过三个字符,那么MYSQL会使用 Turbo Boyer-Moore algorithm算法来初始化查询表达式,然后用这个表达式来让查询更迅速。

查询中有col name IS NULL可以使用colname索引。

任何一个没有覆盖所有WHERE中AND级别条件的索引是不会被使用的。也就是说,要使用一个索引,这个索引中的第一列需要在每个AND组中出现。

下面的WHERE条件会使用索引:

  ... WHERE index_part1=1 AND index_part2=2 AND other_column=3

    /* index = 1 OR index = 2 */
... WHERE index=1 OR A=10 AND index=2

    /* optimized like "index_part1='hello'" */
... WHERE index_part1='hello' AND index_part3=5

    /* Can use index on index1 but not on index2 or index3 */
... WHERE index1=1 AND index2=2 OR index1=3 AND index3=3;

下面的WHERE条件不会使用索引:

      /* index_part1 is not used */
... WHERE index_part2=1 AND index_part3=2

    /*  Index is not used in both parts of the WHERE clause  */
... WHERE index=1 OR A=10

    /* No index spans all rows  */
... WHERE index_part1=1 OR index_part2=10

有时候mysql不会使用索引,即使在可用的情况下。例如当mysql预估使用索引会读取大部分的行数据时。(在这种情况下,一次全表扫描可能比使用索引更快,因为它需要更少的检索)。然而,假如语句中使用LIMIT来限定返回的行数,mysql则会使用索引。因为当结果行数较少的情况下使用索引的效率会更高。

Hash索引特性


Hash类型的索引有一些区别于以上所述的特征:

  • 它们只能用于对等比较,例如=和<=>操作符(但是快很多)。它们不能被用于像<这样的范围查询条件。假如系统只需要使用像“键值对”的这样的存储结构,尽量使用hash类型索引。

  • 优化器不能用hash索引来为ORDER BY操作符加速。(这类索引不能被用于搜索下一个次序的值)

  • MySQL不能判断出两个值之间有多少条数据(这需要使用范围查询操作符来决定使用哪个索引)。假如你将一个MyISAM表或InnoDB表转为一个依靠hash索引的MEMORY表,这可能会影响一些查询。

  • 只有完整的键才能被用于搜索一行数据(使用了B-Tree索引,那么任何一个键的前缀都可以用于查找)。

相关 [tree 索引 hash] 推荐:

B-Tree索引与Hash索引的比较

- - SegmentFault 最新的文章
B-Tree索引与Hash索引的比较. 翻译自 http://dev.mysql.com/doc/refman/5.6/en/index-btree-hash.html. 理解B-Tree和Hash的数据结构能够帮助我们预测不同存储引擎下的查询性能差异. 存储引擎在索引中使用这些数据结构,尤其是 MEMORY 同时提供了B-Tree和Hash索引让你选择.

mysql索引原理之B+/-Tree

- - CSDN博客架构设计推荐文章
索引,是为了更快的查询数据,查询算法有很多,对应的数据结构也不少,数据库常用的索引数据结构一般为B+Tree. 关于B-Tree的官方定义个人觉得比较难懂,通俗一点就是举个例子. 假如:一本英文字典,单词+详细解释组成了一条记录,现在需要索引单词,那么以单词为key,单词+详细解释为data,B-Tree就是以一个二元组{key,data}来定义一条记录.

mysql 索引优化 btree hash rtree

- - 数据库 - ITeye博客
mysql里目前只支持4种索引分别是:b-tree,full-text,hash以及r-tree索引. b-tree索引应该是mysql里最广泛的索引的了,除了archive,基本所有的存储引擎都支持它. 1.b-tree在myisam里的形式和innodb稍有不同. 在innodb里面有两种形态:其一是primary key形态其leafnode里存放的是数据.而且不仅存放了索引键的数据,还存放了其他字段的数据.其二是secondary index,其leafnode和普通的b-tree差不多,只是还存放了指向主键的信息.

B-Tree索引在sqlserver和mysql中的应用

- - CSDN博客数据库推荐文章
在谈论数据库性能优化的时候,通常都会提到“索引”,但很多人其实没有真正理解索引,并没有搞清楚索引为什么能加快检索速度,以至于在实践中并不能很好的应用索引. 事实上,索引可以说是最廉价而且十分有效一种优化手段,一般而言,设计优良的索引对查询性能优化确实能起到立竿见影的效果. 相信很多读者,都了解和使用过索引,可能也看过或者听过”新华字典“、”图书馆“之类比较通俗描述,但是对索引的存储结构和本质任然还比较迷茫.

postgresql hash索引流复制备库报错

- - x-marker的博客
今天测试了一把postgresql的hash索引,在流复制过程中会有些问题,一下是测试过程: 1.首先搭建pg9.3.4的流复制环境,略,我的环境如下:db3为主库,db4为从库. 看下主库数据条数和备库条数:. 主备库的数据一致,表结构也都完全一样,下面测试;. 3.测试hash索引检索:.                                                         QUERY PLAN                                                         .

Oracle B-tree、位图、全文索引三大索引性能比较及优缺点汇总

- - Oracle - 数据库 - ITeye博客
引言:大家都知道“效率”是数据库中非常重要的一个指标,如何提高效率大家可能都会想起索引,但索引又这么多种,什么场合应该使用什么索引呢. 哪种索引可以提高我们的效率,哪种索引可以让我们的效率大大降低(有时还不如全表扫描性能好)下面要讲的“索引”如何成为我们的利器而不是灾难. 多说一点,由于不同索引的存储结构不同,所以应用在不同组织结构的数据上,本篇文章重点就是:理解不同的技术都适合在什么地方应用.

XML to tree XML 树

- Bloger - 博客园-首页原创精华区
前面发了一个 html to tree 再发一个 xml to tree. 版权所有:版权所有(C) 2009. 文件名称:xml2tree.js. 完成日期:2009-12-22. 页:http://www.chaige.net */ var XML2Tree = function (ini) {.

一致性hash

- - 互联网 - ITeye博客
一致性hash算法 - consistent hashing. 分类:  算法艺术2010-02-02 09:19 69836人阅读  评论(97)  收藏  举报. 算法 cache object 服务器 存储 c. 一致性 hash 算法( consistent hashing ).

Hash Collision DoS 问题

- mazhechao - 酷壳 - CoolShell.cn
最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 Hash Collision DoS (Hash碰撞的拒绝式服务攻击),有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比. 这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样,但是key一样数据,然后让你的Hash表成为一张单向链表,而导致你的整个网站或是程序的运行性能以级数下降(可以很轻松的让你的CPU升到100%).

局部敏感Hash

- - xiaobaoqiu Blog
之前在项目中做数据聚合去重的逻辑的时候简单看过局部敏感Hash(Locality Sensitive Hashing,简称LSH)这个东东. LSH可以理解为一种衡量文本相似度的算法,特点是散列前的相似点经过哈希之后,也能够在一定程度上相似,并且具有一定的概率保证. 其有坚实的理论依据(98年左右理论就提出来了,99年有第一版实现)并且在高维数据空间中表现优异.