MySQL的B-Tree索引和Hash索引的区别

发布网友发布时间：2022-04-09 01:53

共3个回答

热心网友时间：2022-04-09 03:23

ash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。
可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多*和弊端，主要有以下这些。

（1）Hash 索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。

由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。

（2）Hash 索引无法被用来避免数据的排序操作。

由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；

（3）Hash 索引不能利用部分索引键查询。

对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。

（4）Hash 索引在任何时候都不能避免表扫描。

前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。

（5）Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

热心网友时间：2022-04-09 04:41

当分片索引不是纯整型的字符串时，只接受整型的内置 hash 算法是无法使用的。为此，stringhash 按照用户定义的起点和终点去截取分片索引字段中的部分字符，根据当中每个字符的二进制 unicode 值换算出一个长整型数值，然后就直接调用内置 hash 算法求解分片路由：先求模得到逻辑分片号，再根据逻辑分片号直接映射到物理分片。

用户需要在 rule.xml 中定义 partitionLength[] 和 partitionCount[] 两个数组和 hashSlice 二元组。

在 DBLE 的启动阶段，点乘两个数组得到模数，也是逻辑分片的数量

并且根据两个数组的叉乘，得到各个逻辑分片到物理分片的映射表（物理分片数量由 partitionCount[] 数组的元素值之和）

此外根据 hashSlice 二元组，约定把分片索引值中的第 4 字符到第 5 字符（字符串以 0 开始编号，编号 3 到编号 4 等于第 4 字符到第 5 字符）字符串用于 “字符串->整型”的转换

在 DBLE 的运行过程中，用户访问使用这个算法的表时，WHERE 子句中的分片索引值会被提取出来，取当中的第 4 个字符到第 5 字符，送入下一步

设置一个初始值为 0 的累计值，逐个取字符，把累计值乘以 31，再把这个字符的 unicode 值当成长整型加入到累计值中，如此类推直至处理完截取出来的所有字符，此时的累计值就能够代表用户的分片索引值，完成了 “字符串->整型” 的转换

对上一步的累计值进行求模，得到逻辑分片号

再根据逻辑分片号，查映射表，直接得到物理分片号

与MyCat的类似分片算法对比

请点击输入图片描述

两种算法在string转化为int之后，和 hash 分区算法相同，区别也继承了 hash 算法的区别。

开发注意点

【分片索引】1. 必须是字符串

【分片索引】2. 最大物理分片配置方法是，让 partitionCount[] 数组和等于 2880

例如：

或

【分片索引】3. 最小物理分片配置方法是，让 partitionCount[] 数组和等于 1

例如

【分片索引】4. partitionLength 和 partitionCount 被当做两个逗号分隔的一维数组，它们之间的点乘必须在 [1, 2880] 范围内

【分片索引】5. partitionLength 和 partitionCount 的配置对顺序敏感

和

是不同的分片结果

【分片索引】6. 分片索引字段长度小于用户指定的截取长度时，截取长度会安全减少到符合分片索引字段长度

【数据分布】1. 分片索引字段截取越长则越有利于数据均匀分布

【数据分布】2. 分片索引字段的内容重复率越低则越有利于数据均匀分布

运维注意点

【扩容】1. 预先过量分片，并且不改变 partitionCount 和 partitionLength 点乘结果，也不改变截取设置 hashSlice 时，可以避免数据再平衡，只需进行涉及数据的迁移

【扩容】2. 若需要改变 partitionCount 和 partitionLength 点乘结果或改变截取设置 hashSlice 时，需要数据再平衡

【缩容】1. 预先过量分片，并且不改变 partitionCount 和 partitionLength 点乘结果，也不改变截取设置 hashSlice 时，可以避免数据再平衡，只需进行涉及数据的迁移

【缩容】2. 若需要改变 partitionCount 和 partitionLength 点乘结果或改变截取设置 hashSlice 时，需要数据再平衡

配置注意点

【配置项】1. 在 rule.xml 中，可配置项为 <property name="partitionLength"> 、<property name="partitionCount"> 和 <property name="hashSlice">

【配置项】2.在 rule.xml 中配置 <property name="partitionLength"> 标签

内容形式为：<物理分片持有的虚拟分片数>[,<物理分片持有的虚拟分片数>,...<物理分片持有的虚拟分片数>]

物理分片持有的虚拟分片数必须是整型，物理分片持有的虚拟分片数从左到右与同顺序的物理分片数对应，partitionLength 和partitionCount 的点乘结果必须在 [1, 2880] 范围内

【配置项】3. 在 rule.xml 中配置 <property name="partitionCount"> 标签内容形式为：<物理分片数>[,<物理分片数>,...<物理分片数>]

其中物理分片数必须是整型，物理分片数按从左到右的顺序与同顺序的物理分片持有的虚拟分片数对应，物理分片的编号从左到右连续递进，partitionLength 和 partitionCount 的点乘结果必须在 [1, 2880] 范围内

【配置项】4. partitionLength 和 partitionCount 的语义是：持有partitionLength[i] 个虚拟分片的物理分片有 partitionCount[i] 个

例如

语义是持有 512 个逻辑分片的物理分片有 1 个，紧随其后，持有 256 个逻辑分片的物理分片有 2 个

【配置项】5.partitionLength 和 partitionCount 都对书写顺序敏感，

例如

分片结果是第一个物理分片持有头512个逻辑分片，第二个物理分片持有紧接着的256个逻辑分片，第三个物理分片持有最后256个逻辑分片，相对的

分片结果则是第一个物理分片持有头 256 个逻辑分片，第二个物理分片持有紧接着的 256 个逻辑分片，第三个物理分片持有最后 512 个逻辑分片

【配置项】6.partitionLength[] 的元素全部为 1 时，这时候partitionCount 数组和等于 partitionLength 和 partitionCount 的点乘，物理分片和逻辑分片就会一一对应，该分片算法等效于直接取余

【配置项】7.在 rule.xml 中配置标签，从分片索引字段的第几个字符开始截取到第几个字符：

若希望从首字符开始截取 k 个字符（ k 为正整数），配置的内容形式可以为“ 0 : k ”、“ k ”或“ : k ”；

若希望从末字符开始截取 k 个字符（ k 为正整数），则配置的内容形式可以为“ -k : 0 ”、“ -k ”或“ -k : ”；

若希望从头第 m 个字符起算截取 n 个字符（ m 和 n 都是正整数），则先计算出 i = m - 1 和 j = i + n - 1，配置的内容形式为“ i : j ”；

若希望从尾第 m 个字符起算截取从尾算起的 n 个字符（ m 和 n 都是正整数），则先计算出 i = -m + n - 1，配置的内容形式可以为“ -m : i ”；

若希望不截取，则配置的内容形式可以为“ 0 : 0 ”、“ 0 : ”、“ : 0 ”或 “ : ”

热心网友时间：2022-04-09 06:15

1. hash索引查找数据基本上能一次定位数据，当然有大量碰撞的话性能也会下降。而btree索引就得在节点上挨着查找了，很明显在数据精确查找方面hash索引的效率是要高于btree的；
2. 那么不精确查找呢，也很明显，因为hash算法是基于等值计算的，所以对于“like”等范围查找hash索引无效，不支持；
3. 对于btree支持的联合索引的最优前缀，hash也是无法支持的，联合索引中的字段要么全用要么全不用。提起最优前缀居然都泛起迷糊了，看来有时候放空得太厉害；
4. hash不支持索引排序，索引值和计算出来的hash值大小并不一定一致。