Btree&B+tree&hash树

树

1、树的特性

1）一棵树中的任意两个结点有且仅有唯一的一条路径连通；

2）一棵树如果有n个结点，则它一定有n−1条边；

3）在一棵树中加一条边将会构成一个回路。

2、二叉树

1）二叉树是一种特殊的树，二叉树的特点是每个结点最多有两个儿子。

2）二叉树使用范围最广，一颗多叉树也可以转化为二叉树。

3、满二叉树

1）二叉树中每个内部节点都有两个儿子，满二叉树所有的叶节点都有相同的深度。

2）满二叉树是一棵深度为h且有2h−1个结点的二叉树。

4、完全二叉树

1）若设二叉树的高度为h，除了第h层外，其他层的结点数都达到最大个数，第h层从右向左连续 缺若干个结点，则为完全二叉树。

5、树的特点

1. 如果一棵完全二叉树的父节点编号为K,则其左儿子的编号是2K,右儿子的结点编号为2K+1

2. 已知完全二叉树的总节点数为n求叶子节点个数：
　　　　　　　　当n为奇数时：（n+1）/2
　　　　　　　　当n为偶数时 : （n）/2

3. 已知完全二叉树的总节点数为n求父节点个数：为：n/2

4. 已知完全二叉树的总节点数为n求叶子节点为2的父节点个数：
　　　　　　　　当n为奇数时：n/2
　　　　　　　　当n为偶数时 : n/2-1

5、如果一棵完全二叉树有N个结点，那么这棵二叉树的深度为【log2（N+1）log2（N+1）】（向上取整）

hash树

1、hash树描述（就是散列树）

1. 散列树选择从2开始的连续质数来建立一个十层的哈希树。

2. 第一层结点为根结点，根结点下有2个结点；

3. 第二层的每个结点下有3个结点；

4. 依此类推，即每层结点的子节点数目为连续的质数。

2、hash树特点

注：关系型数据库中，索引大多采用B/B+树来作为存储结构，而全文搜索引擎的索引则主要采用hash的存储结构，这两种数据结构有什么区别？

1. 如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过一次算法即可找到相应的键值；

2. 当然了，这个前提是，键值都是唯一的，如果键值不是唯一的，就需要先找到该键所在位置，然后再根据链表往后扫描，直到找到相应的数据；

3. 如果是范围查询检索，这时候哈希索引就毫无用武之地了，因为原先是有序的键值，经过哈希算法后，
　　　　　　 有可能变成不连续的了，就没办法再利用索引完成范围查询检索；

4. 同理，哈希索引也没办法利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）；

3、建立hash树

1. 选择从2开始的连续质数来建立一个十层的哈希树。
　　　　　　2. 第一层结点为根结点，根结点下有2个结点；第二层的每个结点下有3个结点；

3. 依此类推，即每层结点的子节点数目为连续的质数。到第十层，每个结点下有29个结点。

4. 同一结点中的子结点，从左到右代表不同的余数结果。
　　　　　　　　例如：第二层结点下有三个子节点。那么从左到右分别代表：除3余0，除3余1，除3余2.对质数进行取余操作得到的余数决定了处理的路径。
5. 以随机的10个数的插入为例，来图解HashTree的插入过程。

6. 其实也可以把所有的键-值节点放在哈希树的第10层叶节点处，这第10层的满节点数就包含了所有的整数个数，
　　　　 　　 但是如果这样处理的话，所有的非叶子节点作为键-值节点的索引，这样使树结构庞大，浪费空间。

4、查找编辑

1. 哈希树的节点查找过程和节点插入过程类似，就是对关键字用质数序列取余，根据余数确定下一节点的分叉路径，直到找到目标节点。

2. 如上图，最小”哈希树(HashTree)在从4G个对象中找出所匹配的对象，比较次数不超过10次，也就是说：最多属于O(10)。

3. 在实际应用中，调整了质数的范围，使得比较次数一般不超过5次。

4. 也就是说：最多属于O(5)，因此可以根据自身需要在时间和空间上寻求一个平衡点。

5、删除编辑

1. 哈希树的节点删除过程也很简单，哈希树在删除的时候，并不做任何结构调整。

2. 只是先查到到要删除的节点，然后把此节点的“占位标记”置为false即可（即表示此节点为空节点，但并不进行物理删除）。

6、hash树优点

1）结构简单

1. 从哈希树的结构来说，非常的简单，每层节点的子节点个数为连续的质数。
　　　　　　　　2. 子节点可以随时创建，因此哈希树的结构是动态的，也不像某些哈希算法那样需要长时间的初始化过程。
　　　　　　　　3. 哈希树也没有必要为不存在的关键字提前分配空间。

2）查找迅速

1. 从算法过程我们可以看出，对于整数，哈希树层级最多能增加到10。
　　　　　　　　2. 因此最多只需要十次取余和比较操作，就可以知道这个对象是否存在，这个在算法逻辑上决定了哈希树的优越性。

3）结构不变

1. 从删除算法中可以看出，哈希树在删除的时候，并不做任何结构调整。

2. 常规树结构在增加元素和删除元素的时候都要做一定的结构调整，否则他们将可能退化为链表结构，而导致查找效率的降低。

3. 哈希树采取的是一种“见缝插针”的算法，从来不用担心退化的问题，也不必为优化结构而采取额外的操作，因此大大节约了操作时间。

7、hash树缺点

1. 哈希树不支持排序，没有顺序特性。

2. 如果在此基础上不做任何改进的话并试图通过遍历来实现排序，那么操作效率将远远低于其他类型的数据结构。

8、hash索引使用范围

总结：哈希适用在小范围的精确查找，在列数据很大，又不需要排序，不需要模糊查询，范围查询时有用

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-tree/B+tree

1. 以一个3阶的B-Tree举例

1. 每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。
2. 两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。
3. 以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。
   ‘’‘模拟查找关键字29的过程：’’’

# 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
# 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
# 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
# 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
# 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
# 在磁盘块8中的关键字列表中找到关键字29。

Btree的特点：

（1）所有键值分布在整个树中
（2）任何关键字出现且只出现在一个节点中
（3）搜索有可能在非叶子节点结束
（4）在关键字全集内做一次查找，性能逼近二分查找算法

2. B+tree(以每个节点可存4个建值及指针信息为例)

1. B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息
2. 在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。
3. 因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

B+tree的特点：

（1）所有关键字存储在叶子节点，非叶子节点不存储真正的data
（2）为所有叶子节点增加了一个链指针

B+Tree优点

1. InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节

2. 也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（这里的K取值为〖10〗^3）。

3. 也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。

说明：

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。

mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

btree和B+tree的区别：
(1)B+tree的非叶子节点不存储真正的data，而btree可以
(2)增加了一个链指针
(3)btree支持数据的延展性，B+tree支持数据的扩展性

B-tree与哈希索引的区别

1）B+tree的索引：

是按照顺序存储的，所以，如果按照B+tree索引，可以直接返回，带顺序的数据，但这个数据只是该索引列含有的信息。因此是顺序I/O

适用于： 精确匹配 、范围匹配 、最左匹配

2）Hash索引：

索引列值的哈希值+数据行指针：因此找到后还需要根据指针去找数据，造成随机I/O

适合： 精确匹配

不适合： 模糊匹配 、范围匹配 、不能排序

参考原址来自于此