Hash 树

hash树

**注：**关系型数据库中，索引大多采用B/B+树来作为存储结构，而全文搜索引擎的索引则主要采用hash的存储结构，这两种数据结构有什么区别？
1.如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过一次算法即可找到相应的键值；
2.当然了，这个前提是，键值都是唯一的，如果键值不是唯一的，就需要先找到该键所在位置，然后再根据链表往后扫描，直到找到相应的数据；
3.如果是范围查询检索，这时候哈希索引就毫无用武之地了，因为原先是有序的键值，经过哈希算法后，　　　　　　有可能变成不连续的了，就没办法再利用索引完成范围查询检索；
4.同理，哈希索引也没办法利用索引完成排序，以及like‘xxx%’这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）；

1.选择从2开始的连续质数来建立一个十层的哈希树。
2.第一层结点为根结点，根结点下有2个结点；第二层的每个结点下有3个结点；
3.依此类推，即每层结点的子节点数目为连续的质数。到第十层，每个结点下有29个结点。
4.同一结点中的子结点，从左到右代表不同的余数结果。
例如：第二层结点下有三个子节点。那么从左到右分别代表：除3余0，除3余1，除3余2.对质数进行取余操作得到的余数决定了处理的路径。
5.以随机的10个数的插入为例，来图解HashTree的插入过程。
6.其实也可以把所有的键-值节点放在哈希树的第10层叶节点处，这第10层的满节点数就包含了所有的整数个数，　　　　　但是如果这样处理的话，所有的非叶子节点作为键-值节点的索引，这样使树结构庞大，浪费空间。

1）结构简单
- 1.从哈希树的结构来说，非常的简单，每层节点的子节点个数为连续的质数。
- 2.子节点可以随时创建，因此哈希树的结构是动态的，也不像某些哈希算法那样需要长时间的初始化过程。
- 3.哈希树也没有必要为不存在的关键字提前分配空间。
2）查找迅速
- 1.从算法过程我们可以看出，对于整数，哈希树层级最多能增加到10。
- 2.因此最多只需要十次取余和比较操作，就可以知道这个对象是否存在，这个在算法逻辑上决定了哈希树的优越性。
3）结构不变
- 1.从删除算法中可以看出，哈希树在删除的时候，并不做任何结构调整。
- 2.常规树结构在增加元素和删除元素的时候都要做一定的结构调整，否则他们将可能退化为链表结构，而导致查找效率的降低。
- 3.哈希树采取的是一种“见缝插针”的算法，从来不用担心退化的问题，也不必为优化结构而采取额外的操作，因此大大节约了操作时间。

**总结：**哈希适用在小范围的精确查找，在列数据很大，又不需要排序，不需要模糊查询，范围查询时有用
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值相关联。
- 这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。