B树索引和Hash索引的应用场景和区别 关系型数据库中,索引大多采用B/B+树来作为存储结构,而全文搜索引擎的索引则主要采用hash的存储结构,这两种数据结构有什么区别?如果是等值查询,那么哈希索引明显有绝对优势,因为只需要经过一次算法即可找到相应的键值;当然了,这个前提是,键值都是唯一的。如果键值不是唯一的,就需要先找到该键所在位置,然后再根据链表往后扫描,直到找到相应的数据; 从示意图中也能看到,如果是范围查询检索,这时候哈希索引就毫无用武之地了,因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索;同理,哈希索引也没办法利用索引完成排序,以及like ‘xxx%’ 这样的部分模糊查询(这种部分模糊查询,其实本质上也是范围查询); 哈希索引也不支持多列联合索引的最左匹配规则; B+树索引的关键字检索效率比较平均,不像B树那样波动幅度大,在有大量重复键值情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题 hash结构的特点:检索效率非常高,索引的检索可以一次到位,O(1)。B树需要从根节点到枝节点,最后才能到叶节点进行多次I/O操作,所以hash的效率远远高于B树的效率。 那么为什么数据库索引还是用B树结构呢? 1、hash索引仅满足“=”、“IN”和“<=>”查询,不能使用范围查询因为hash索引比较的是经常hash运算之后的hash值,因此只能进行等值的过滤,不能基于范围的查找,因为经过hash算法处理后的hash值的大小关系,并不能保证与处理前的hash大小关系对应。 2、hash索引无法被用来进行数据的排序操作由于hash索引中存放的都是经过hash计算之后的值,而hash值的大小关系不一定与hash计算之前的值一样,所以数据库无法利用hash索引中的值进行排序操作。 3、对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。 4、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。 对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。(因此:键值重复率低的适合用B树索引) b-tree完全基于key的比较,和二叉树相同的道理,相当于建个排序后的数据集,使用二分法查找算法,实际上也非常快,而且受数据量增长影响非常小。B+树索引和哈希索引的区别转自:https://www.cnblogs.com/bonelee/p/6224698.html 哈希文件也称为散列文件,是利用哈希存储方式组织的文件,亦称为直接存取文件。它类似于哈希表,即根据文件中关键字的特点,设计一个哈希函数和处理冲突的方法,将记录哈希到存储设备上。 在哈希文件中,是使用一个函数(算法)来完成一种将关键字映射到存储器地址的映射,根据用户给出的关键字,经函数计算得到目标地址,再进行目标的检索。 转自:http://imysql.com/2016/01/06/mysql-faq-different-between-btree-and-hash-index.shtml B+树索引和哈希索引的区别 一个经典的B+树索引数据结构见下图:
B+树是一个平衡的多叉树,从根节点到每个叶子节点的高度差值不超过1,而且同层级的节点间有指针相互链接。 在B+树上的常规检索,从根节点到叶子节点的搜索效率基本相当,不会出现大幅波动,而且基于索引的顺序扫描时,也可以利用双向指针快速左右移动,效率非常高。因此,B+树索引被广泛应用于数据库、文件系统等场景。而哈希索引的示意图则是这样的:
(图片源自网络) 简单地说,哈希索引就是采用一定的哈希算法,把键值换算成新的哈希值,检索时不需要类似B+树那样从根节点到叶子节点逐级查找,只需一次哈希算法即可立刻定位到相应的位置,速度非常快。 从上面的图来看,B+树索引和哈希索引的明显区别是: 如果是等值查询,那么哈希索引明显有绝对优势,因为只需要经过一次算法即可找到相应的键值;当然了,这个前提是,键值都是唯一的。如果键值不是唯一的,就需要先找到该键所在位置,然后再根据链表往后扫描,直到找到相应的数据; 从示意图中也能看到,如果是范围查询检索,这时候哈希索引就毫无用武之地了,因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索; 同理,哈希索引也没办法利用索引完成排序,以及like ‘xxx%’ 这样的部分模糊查询(这种部分模糊查询,其实本质上也是范围查询); 哈希索引也不支持多列联合索引的最左匹配规则; B+树索引的关键字检索效率比较平均,不像B树那样波动幅度大,在有大量重复键值情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题。 后记通常,B+树索引结构适用于绝大多数场景,像下面这种场景用哈希索引才更有优势:在HEAP表中,如果存储的数据重复度很低(也就是说基数很大),对该列数据以等值查询为主,没有范围查询、没有排序的时候,特别适合采用哈希索引 例如这种SQL:SELECT … FROM t WHERE C1 = ?; — 仅等值查询 大多数场景下,都会有范围查询、排序、分组等查询特征,所以数据库使用B+树索引。转自:https://blog.csdn.net/
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/86616.html