一、Hash结构
● Hash本身是一个函数，又被称为散列函数，可以帮助我们大幅提升检索数据的效率
● Hash算法是通过某种确定性的算法将输入转变为输出。相同的输入永远可以得到相同的输出
● 加速查找速度的数据结构，常见的有两类：
○ 树。比如平衡二叉搜索树，查询/修改/删除的平均时间复杂度都是O(log2N)
○ 哈希。例如HashMap，查询/插入/修改/删除的平均时间复杂度都是O(1)
● 采用Hash进行精确检索效率非常高，基本上一次检索就可以找到，而B+树需要自顶向下依次查找，多次访问节点
● 哈希碰撞：数据库采用链接法来解决
二、二叉搜索树
1.二叉树的特点：
● 一个节点只能有两个子节点，也就是一个节点分支不能超过2
● 左子节点 < 本节点；右子节点 >= 本节点；比我大的向左，小的向右
● 磁盘的I/O次数和索引树的高度是相关的
2.查找/插入规则
● 如果key大于根节点，则在右子树中进行查找；
● 如果key小于根节点，则在左子树中进行查找
● 如果key等于根节点，返回根节点即可
3.特殊情况下二叉树效率变慢
顺序插入数据，树的高度越来越高，磁盘I/O次数相应增加，相当于退化成了链表，查找数据的时间复杂度变成了O(n)。
三、AVL树(平衡二叉搜索树)
1.AVL树的性质：
它是一颗空树或它的左右两个子树的高度差绝对值不超过1，并且左右两个子树都是一颗平衡二叉树
2.每访问一次节点就需要一次磁盘I/O，对于上面的树来说，需要进行5次I/O操作。虽然平衡二叉树的效率高，但树的深度也同样高，磁盘I/O增加，降低查询效率。
四、B-Tree
1.B树的英文是Balance Tree，也就是多路平衡查找树，树的分叉树越来越大，它的高度远小于二叉树，就需要把树瘦高变成矮胖
2.一个M阶的B树(M>2)有以下的特性：
● 根节点的儿子数的范围是(2,M]
● 每个中间节点包含k-1个关键字和k个孩子，孩子的数量=关键字的数量+1，k的取值范围为 [ ceil(M/2), M ]
● 叶子节点包括k-1个关键字(叶子节点没有孩子)，k的取值范围为[ ceil(M/2), M ]
● 所有叶子节点位于同一层
3.B树总结：
● B树在插入和删除节点的时候如果导致树不平衡，就通过自动调整节点的位置来保持树的自平衡
● 关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据。搜索有可能在非叶子节点结束
其搜索性能等价于在关键字全集内做一次二分查找
五、B+Tree
1.B+树也是一种多路搜索树，基本B树做出了改进，主流的DBMS都支持B+Tree树的索引方式。相比于B树，B+Tree适合文件索引系统
2.B+树和B树的差异在于以下几点：
● 有k个孩子的节点就有k关键字。而B树中，孩子数量=关键字+1
● 非叶子节点的关键字也会同时存在子节点中，并且是在子节点中所有关键字的最大(或最小)
● 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中，而B树中，非叶子节点即保存索引，也保存数据记录
● 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接
● B+树所有的关键字都出现在叶子结点中，叶子节点中会有指针，数据又是递增的，使得我们可以通过指针连接查找，而B树则需要通过中序遍历才能完成查找，效率低很多
思考题：为了减少I/O，索引树会一次性加载吗？
● 数据库索引是存储在磁盘上的，如果数据量大，会导致索引的大小也很大，超过几个G
● 利用索引查询时，逐一加载每一个磁盘页，因为磁盘页对应着索引树的节点
Hash结构效率高，为什么索引结构要设计成树形？
● Hash索引仅能满足=、<>、和IN查询。如果进行范围查询，哈希型的索引，时间复杂度会退化为O(n)；而树形的有序特性，依然能够保持O(log2N)的高效率
● 数据的存储是没有顺序的，在order by情况下，使用Hash索引还需要对数据进行重新排序
● 对于联合索引的情况，Hash值是将联合索引键合并后一起来计算的，无法对单独的一个键或者几个索引键进行查询
● 对于等值查询来说，通常Hash索引的效率更高，不过如果索引列的重复值如果很多，效率会降低。因为遇到Hash冲突时，需要遍历桶中的行指针来进行比较，非常耗时，所以Hash索引不会用到重 复值多的列上
Hash索引与B+树索引的区别：
● Hash索引不能进行范围查询
● Hash索引不支持联合索引的最左原则
● Hash索引不支持order by排序，也无法模糊查询
因篇幅问题不能全部显示，请点此查看更多更全内容