二叉查找树.B树.B+树.hash索引

Mysql数据库的数据结构

二叉查找树

每个存储快存储的是本身关键字和指向孩子的指针
对于树来说存储快就是结点
每个存储快能存储的关键字越多 频繁出入存储快的IO次数越少
如果能指向的孩子越多 树的奥都就越小

二叉查找树 左右子树差要小于1 时间复杂度O（logn）
二叉树结点只能指向2个孩子 每个节点是一个存储快 每个存储快只可以存储两个节点
可是我们需要做到：
降低时间复杂度（高度）
降低IO次数（存储块少）

除此之外二叉查找树还要为了左右相差1 不断的调整平衡

B树

每个节点有多个孩子（降低高度）
每个结点能存储许多关键字（减少IO次数 不会频繁出存储快）

在每一个树结点中关键字必须排序从左到右
关键字的个数比孩子的个数少一个

B+树

• 非叶子结点的关键字是和孩子指针一样多的（相对B树每个结点能存储更 多的关键字 存储更多的关键字树就更矮胖 查找的层数就更少 ）
• 非叶子结点只用来做索引 所有的数据存储在叶子结点
  （查找的层数更加少了 都存储在叶子结点 所以不用像B树 走很多层并且实实在在的查每个关键字 B+树一路直接到关键字）

以上两个优点：每个结点存储更多关键字+都在叶子上更加矮胖

• 所有叶子结点大小顺序排序 形成链 链与链之间又相连 便于范围查找
  便于范围查找是说 找10 可以横向跨子树统计
  
  总结：
  1行或者多行数据（关键字）存储到各个块当中
  每个块之间依靠指针来联系

查询数据库的时候就是从众多存储快当中搜索想要的关键字
块所能容纳的关键字越少 频繁出入块的次数越多 IO次数越多
块所能容纳的关键字越少 块个数越多 树高度容易越高 时间复杂度查询越高

B树解决了这个问题但是在扫描的时候
B+树更加优秀因为能够做到范围同级 跨子树找
B树还有回溯结点接着查找
B+树又做到了更加矮胖 IO次数更加少

HASH索引

不需要从根节点出发查询


有些数据库会使用hash索引

hash索引的结构需要hash运算最终通过返回的hashcode%bucket.length确定具体的桶位置 这个hash操作就已经打乱了结点的大小排序
绝对不会像B+树一样支持范围索引 能够横跨子树 因为每一个桶位置的链都未必有关系
更何况桶与桶之间
所以只能使用 IN == 这种精确的查找 进过HASH之后都是确定的数组下标对应确定的位置

• 组合索引 hash不是单独的索引 B+树支持部分索引
• 无法避免表扫描是 每一次并不是确定唯一的关键字 而是及时找到了那个bucket[i]还要去比较每个链
• 某个bucket[i]的链很长

bitMap

男女 用位图索引 类似于B+树