数据库

BTREE与HASH的区别

2018-07-12  本文已影响758人  半亩房顶

引子

近期入库一批较大数据时候发现有时候查询速度快，而有时候查询速度慢，主要是在使用
like 查询数据时候发现的，%xxx%， xxx% 两个的条件的速度差异很是明显，此问题以前也遇到过，原因就是xxx%时可以命中索引，而 %xxx%时无法命中索引，但此次借此问题有了一些引申思考，数据库的索引方式是什么，如何实现的呢？

一、引申查出 B-Tree 与 hash 两种索引方式，先来看一下他们的特点。

源自：http://dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html。

对于 B-tree 和 hash 数据结构的理解能够有助于预测不同存储引擎下使用不同索引的查询性能的差异，尤其是那些允许你选择 B-tree 或者 hash 索引的内存存储引擎。

B-Tree 索引的特点

B-tree 索引可以用于使用 =, >, >=, <, <= 或者 BETWEEN 运算符的列比较。如果 LIKE 的参数是一个没有以通配符起始的常量字符串的话也可以使用这种索引。比如，以下 SELECT 语句就使用索引：

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

在第一个句子中，只会考虑 'Patrick' <= key_col < 'Patricl' 的记录。第二句中，则只会考虑 'Pat' <= key_col < 'Pau' 的记录。
以下 SELECT 语句不使用索引：

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

第一句里面，LIKE 的值起始于一个通配符。在第二句里，LIKE 的值不是一个常量。如果你这样使用： ... LIKE '%string%'，其中的 string 不大于三个字符，MySql 将使用 Turbo Boyer-Moore 算法来对该字符串表达式进行初始化，并使用这种表达式来让查询更加迅速。如果 col_name 列创建了索引，那么一个使用了 col_name IS NULL 的查询是可以使用该索引的。任何没有涵盖 WHERE 从句中所有 AND 级别的条件的索引将不会被使用。换句话讲，要想使用索引，该索引的前导列必须在每一个 AND 组合中使用到。
以下 WHERE 从句使用索引：

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

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

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

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

这些 WHERE 从句不使用索引：

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

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

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

有时，即使有索引可以使用，MySQL 也不使用任何索引。发生这种情况的场景之一就是优化器估算出使用该索引将要求 MySql 去访问这张表的绝大部分记录。这种情况下，一个表扫描可能更快，因为它要求更少量的查询。但是，如果这样的一个查询使用了 LIMIT 来检索只是少量的记录时，MySql 还是会使用索引，因为它能够更快地找到这点记录并将其返回。

Hash 索引的特点

Hash 索引有着与刚才所讨论特点的相比截然不同的特点：

二、我们应该知其然知其所以然，以下是两种索引的实现原理

首先是 B-Tree

源自：https://www.cnblogs.com/harderman-mapleleaves/p/4528212.html
数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B_TREE。B_TREE索引加速了数据访问，因为存储引擎不会再去扫描整张表得到需要的数据；相反，它从根节点开始，根节点保存了子节点的指针，存储引擎会根据指针快速寻找数据。

image 
    上图显示了一种索引方式。左边是数据库中的数据表，有col1和col2两个字段，一共有15条记录；右边是以col2列为索引列的B_TREE索引，每个节点包含索引的键值和对应数据表地址的指针，这样就可以都过B_TREE在O(logn)的时间复杂度内获取相应的数据，这样明显地加快了检索的速度。

==============================================================================================================================

B_TREE（来源于数据结构，做个收藏）

1、B_TREE的定义

B_TREE是一种平衡多叉排序树，是一种动态查找效率很高的树形结构。B_TREE中所有结点的孩子结点的最大值称为B_TREE的阶，B_TREE的阶通常用m表示，简称为m叉树。一般来说，应该是m>=3。一颗m阶的B_TREE或是一颗空树，或者是满足下列条件的m叉树：

一棵4阶B_TREE的示例。4叉树结点的孩子结点的个数范围[2,4]。其中，有2个结点有4个孩子结点，有1个结点有3个孩子结点，有5个结点有2个孩子结点。

一棵4阶B_TREE

2、B_TREE的查找

在B_TREE上查找x，现将x的关键字与根结点的n个关键字di逐个比较，然后做如下处理：

3、B_TREE的插入

将元素x插入到B_TREE的过程为：

4、B_TREE的删除

定义要删除结点x的关键字的个数为n，l=(int)m/2；

然后是 hash 索引

源自：https://www.cnblogs.com/yimixiong/p/7401527.html
哈希索引是基于哈希表实现的。只有精确匹配索引所有列的的查询才有效。他的实现是存储殷勤会对每一行数据的索引列计算哈希码，并将哈希码和指向该记录的指针维护起来，对于hash相同的，采用链表的方式解决冲突。类似于hashmap。因为索引的结构是十分紧凑的，所以hash索引的查询很快。如此其实我们就很容易的理解hash索引的优缺点了：
1，hash索引只包含了哈希值和行指针，索引不能避免读取行，不能使用覆盖索引。
2，hash索引并不是按照索引顺序存储的，无法用于排序。
3，hash索引不支持部分或者区域查找，部分列的hash结果是不同的。

在Mysql中InnoDB引擎有一个特殊的功能叫做自适应哈希索引，他会在内存中基于B-Tree索引的基础上面创建一个哈希索引，这让B-Tree索引页具备了一些哈希索引的优点。
在《高性能的Mysql》这本树中，作者举了一个自定义哈希索引的列子。假设我们在一个表中大量存储了URL，而且需要根据URL来进行查找。因为URL比较长，这个时候如果我们使用B-Tree索引来，索引会非常的大。解决的办法是在列表中增加一个列，用来存放URL的哈希值，可以通过CRC32对URL进行计算，并存放在列表中，在查找的时候通过CRC32对url进行计算匹配列表中的hash值。
但是这个地方需要注意hash冲突的问题，所以在查询的时候需要添加url的匹配。
例如：where url_crc=CRC32(“http://www.cnblogs.com/yimixiong/p/7400914.html”) and url=” http://www.cnblogs.com/yimixiong/p/7400914.html”

上一篇下一篇

猜你喜欢

热点阅读