树和Hash结构<br>测试链接：https://www.cs.usfca.edu/~galles/visualization/BST.html
二叉查找树
数据结构
缺点
可能会形成一个单向链表,对于读取某个指定节点时效率会很低.
含义
:左子树的键值小于根的键值，右子树的键值<br>大于根的键值。 每个节点分别保存字段数据和一个指向对应数据记录物理地址的指针.
平衡二叉树 (AVL Tree)
含义
在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1
优点
叶子节点的层级减少
形态上能够保持平衡
查询效率提升,大量的顺序插入也不会导致查询性能的降低.
缺点
一个节点最多分裂出两个子节点, 树的高度太高,导致IO次数过多
节点里面只保存着一个关键字,每次操作获取的目标数据太少
B-Tree
思想设计
每个节点尽可能多的存储一些数据,每次磁盘IO就能多加载一些数据到内存,减少磁盘IO
含义
B-Tree是一种平衡的多路查找树,B树允许一个节点存放多个数据
B-Tree的阶=B-Tree中所有节点的子树个数的最大值【B-Tree的每个节点的元素可以视为一次I/O读取，树的高度表示最多的I/O次数】
满足条件
每个节点最多拥有m-1个关键字(根节点除外),也就是m个子树
根节点至少有两个子树(可以没有子树,有就必须是两个)
分支节点至少有(m/2)颗子树 (除去根节点和叶子节点其他都是分支节点)
所有叶子节点都在同一层,并且以升序排序
图
结构存储索引的特点
key为记录的键值，对应表中的主键值(聚 簇索引)
data为一行记录中除主键外的数据
模型图
查找步骤
首先要查找节点,因为B-Tree通常是在磁盘上存储的,所以这步需要进行磁盘IO操作<br>
第二步查找关键字,当找到某个节点后将该节点读入内存中, 然后通过顺序或者折半查找来查找关键<br>字,如果命中就结束查找。
若没有找到关键字，则需要判断大小来找到合适的分支继续查找,如果已经找到了叶子节点,就结束<br>查询。
模型图
总结
优点: B树可以在内部节点存储键值和相关记录数据，因此把频繁访问的数据放在靠近根节点的位<br>置将大大提高热点数据的查询效率。
缺点: B树中每个节点不仅包含数据的key值,还有data数据. 所以当data数据较大时,会导致每个节点<br>存储的key值减少,并且导致B树的层数变高.增加查询时的IO次数.
使用场景: B树主要应用于文件系统以及部分数据库索引，如MongoDB，大部分关系型数据库索引<br>则是使用B+树实现
B+Tree
含义
B+Tree是在B-Tree基础上的一种优化，使其更适合实现存储索引结构，InnoDB存储引擎就是用B+Tree 实现其索引结构。
特征
非叶子节点只存储键值信息.
所有叶子节点之间都有一个链指针.
数据记录都存放在叶子节点中.
图形模式
优势
降低树的高度，增大节点存 储数据量
扫库和扫表能力更强【如果我们要根据索引去进行数据表的扫描，对B Tree进行扫描，需 要把整棵树遍历一遍，而B+Tree只需要遍历他的所有叶子节点即可(叶子节点之间有引用)】
磁盘读写能力更强【加载到磁盘的关键字信息更多】
排序能力更强，如上面的图中可以看出，B+Tree天然具有排序功能。【他的根节点和支节点不保存数据区，所有根节点和支节点同样大小的 情况下，保存的关键字要比B Tree要多】
查询效率更加稳定，每次查询数据，查询IO次数一定是稳定的
一颗B+Tree可以存放多少数据【4292 8704(3阶)】<br>
Hash索引
优点
等值比较查询，而不包 含排序或范围查询的需求，都适合使用哈希索引
没有哈希冲突的情况下,等值查询访问哈希索引的数据非常快
缺点
哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。
哈希索引只支持等值比较查询。不支持任何范围查询和部分索引列匹配查找。
哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
模型图
