03-索引结构、实现及使用

Charlie
  2024-03-11 14:03 2024-03-11 14:03 创建   2024-07-05 12:55:04 2024-07-05 12:55:04 更新    

1. 索引

  • 索引：是一种排序的数据结构，协助快速查询、更新数据库表中的数据

    • B+ Tree
    • 基于磁盘存储，堆文件/随机文件

  • 目标

    1. 高扇出：改善邻近键的数据局限性(每个块的节点尽量多)
    2. 低高度：减少遍历期间的寻道次数

2. 👍B Tree/B+Tree结构

  • B+ Tree

    1. 内部节点只存key，不存value
    2. 叶节点才存value （和B Tree的主要区别）
    3. 相邻叶节点之间有指针->为了方便范围查询

  • 每个节点刚好放在一个Page里（硬盘存储最小单元）

  • 每个节点最多N个键和N+1个指向节点的指针

  • 占用率：节点容量和实际持有键的数量之间的关系

    • 一般是50%
    • 如果太紧凑，不利于写，一旦增加都需要大幅修改树的结构

  • 为什么不用BST：适合内存搜索，但不适合磁盘搜索

3. B树查找算法

  • 算法复杂度从两个角度讨论：块传输，键比较

  • 块传输：

    • 块传输数量等于树高H

  • 比较次数：对数基数为2，二分查找，每次比较，搜索空间减半，复杂度为logM

  • B+Tree 块数量的设计

    • 内部节点: key和指针
    • 叶节点: key,value和指针
    • 数量不能确定

4. 👍B树的分裂

插入节点，可能导致分裂

  1. 分配一个新节点
  2. :一半元素从分裂节点复制到新节点
  3. 新元素放入相应的节点
  4. 在分裂节点的父节点处，添加一个分割键和指向新节点的指针

4.1. 叶节点分裂

  • 叶节点分裂：把value复制到下一块，向上传递
    1. 查找算法定位目标叶节点，并将新值关联
    2. 有空就插⼊，没空就叫“节点溢出”overflow，必须分裂
      • C1:叶节点：超过Max（N）最多容纳N个键值对
      • C2:非叶节点：指针超过Max（N+1）
    3. 分裂：分配新节点，将⼀半元素从原分裂节点传输给它，并添加它的第⼀个键和指向⽗节点的指针，这时候，键被提升了（promote）。执⾏分裂的数组下标称之为分裂点（也叫中点），分裂点之后的所有元素被传输到新创建的兄弟节点

4.2. 非叶节点分裂

image.png

  • 非叶节点分裂：直接把Key分割点放到上层
    1. 创造新节点
    2. 把原节点N/2 + 1移到下一节点
    3. 分裂点的键被提升到⽗⼀级
    4. 插⼊要插⼊的节点
    5. ⽣成额外指针，指向新裂变的节点

保证50%占用率

5. 👍B树的合并

删除节点，可能导致合并

5.1. 叶节点合并

  • 判定条件：节点最大容量N个key-value，N+1个指针
    • 叶节点：key-value的数量是否小于等于N，把上面的key删除
    • 非叶节点：指针数量是否小于等于N+1，把上面的key下移

⼀般50%是树状结构节点占用率的阈值N

e.g.删除16
image.png

5.2. 非叶节点合并

  • 假设元素已经删除，则合并步骤：
    1. 从右节点复制所有元素去左节点，删除右节点
    2. 从父节点删除右节点指针（非叶节点则降级）

e.g.删除10
image.png

  • 问题：分裂合并导致IO过于频繁
    • 不同公司在分裂时一致，但合并有不同优化策略
  • 解决思路：
    1. 按照存储空间的占比设置阈值，而不是key-value/指针的数量
    2. 再平衡，控制平衡的个数

6. B+树的分裂/合并

B树和B+树的插入、删除图文详解 - nullzx - 博客园

7. B树索引能做什么

  1. 全键值 WHERE x=123
  2. 键值范围 WHERE 45 < x <232
  3. 键前缀查找 WHERE x LIKE ‘J%’

除了这三个，其他查询都用不上B树索引。

8. 索引结构

T(id,b,c,d)

  1. 二级索引直接指向数据不使用主索引
    • 对读有利
  2. 二级索引指向主索引
    • 对写有利，发生修改时只需要修改主索引
    • 读效率低

image.png

9. 索引的问题

9.1. 开销

  1. 磁盘开销
    • 基本表可能只占存储空间的小部分，大部分是索引
  2. 处理的开销
    • 插入数据也要同时插入索引，会导致合并和删除，过多的索引导致插入速度过慢
    • 索引本身也有锁

9.2. 压缩

  1. 主要针对叶节点的value压缩，key值很难压缩
  2. 一般是对复合键索引压缩

9.3. 索引会降低查询效率吗

有可能，如果表很小可能全表查询的效率比索引高

  • 索引和目录
    • 两种完全不同的机制
    • 索引是一种以原子粒度访问数据库的手段而不是为了检索大量数据的

10. 判断索引适用性

  • 依据是检索比例

    • 经验数据是10%
    • 只能通过test验证索引的效果

  • 什么时候用B树索引

    1. 仅需要通过索引访问基本表的很少一部分
    2. 如果要处理表中的多行数据，可以减少读取基本表的操作
      1. 如果Index(x,y), 则SELECT x,y FROM T WHERE就可以只使用索引不使用基本表

11. 其它索引

11.1. Hash索引

11.1.1. 特点

  1. 只能做全键值索引，时间/空间效率都很高
  2. 问题：
    1. 无法完成其它查询
    2. 碰撞率问题
      • 一般需要构建10倍左右的容量，降低碰撞率
  3. 哈希值一般直接当成地址使用，一次IO操作直接得到数据的地址
  4. 一般是在内存中构建
  • 例子
    • 身份证：很长，相同前缀非常多，字符串，要一位位匹配。通过哈希索引映射成数值，查询效率奇高。

11.1.2. Hash函数

  1. 直接定址：地址数量少，key比较连续分布均匀
  2. 平方取中：把原来分散的key值变得比较均匀，特别是对于大规模函数
    1. 取中间几位
  3. 除留余数法

11.1.3. Hash碰撞

  1. 闭散列 Separate Chaining
  2. 开散列 Open Addressing

11.2. 位图索引

可以进行压缩，可以快速获取某个值最早出现在哪个ID字段里

image.png

11.2.1. 适用场景

分类取值（每个字段取值较少），大量组合查询

11.2.2. 位图联结索引

  • 允许使用另外某个表的列对⼀个给定表建立索引。实际上，这就是允许对⼀ 个索引结构（⽽不是表本身）中的数据进⾏逆规范化。

image.png

好的搜索：隐含检索条件，分页，搜索框下面加一句吹牛的话

11.3. 函数索引

原来是对X的值构建索引，但现在对f(x)=A进行索引

11.3.1. 适用场景

  1. 不区分大小写查询
  2. T,F的巨大差异下的索引
    1. True 99%, False 1%。使用函数把True映射到null，把false映射到随机数，然后对fase构建B树索引。
  3. 有选择的唯一性

image.png

12. 索引和外键

任何一张表T(id, …)，系统会缺省地给主键构建索引

  • 系统地对表的外键加上索引的做法非常普遍，
    1. 原因：出现级联的处理过程时防止死锁
    2. 例外：外键更新非常少，如代码表

12.1. 同一字段，多个索引

字段顺序：实践中往往把可能会变化的字段放到前面，可以只构建复合索引而不用为这个字段单独构建索引。

orders(oid,aid,…)，变动频繁
articles(aid,name,…)，类似代码表不需要经常变动
多对多需要一张order_details(oid,aid)表，复合主键(oid,aid)，不需要单独为oid构建外键索引。

如果order_details(aid, oid)，复合主键(oid, aid)，还需要为oid单独构建一个外键索引，会导致多余索引

image.png

12.2. 系统生成键

  • 系统生成序列号，远好于
    1. 寻找当前最大值，并+1
    2. 用一个专用表保存“下一个值”并加锁更新
  • 但如果插⼊并发性过⾼，在主键索引的创建操作上会发⽣⼗分严重的资源竞争
  • 解决方案
    1. 反向键索引或逆向索引 reverse index
      • 函数索引的一种
    2. 哈希索引 hash index

12.3. 为什么没有使用索引

  1. 我们在使用B+树索引，⽽且谓词中没有使用索引的最前列
    • T,T(X,Y)有索引，做SELECT * FROM T WHERE Y=5
    • 本质是对X的索引
  2. 使用SELECT COUNT(*) FROM T，⽽且T上有索引，但是优化器仍然全表扫描
  3. 对于⼀个有索引的列作出函数查询
    • Select * from t where f(indexed_col) = value
    • 函数值和参数顺序不同
  4. 隐形函数查询
    • 用于在关系型数据库中执行多个表之间的连接操作，而无需显式地编写JOIN子句。它通过定义表之间的外键关系，让数据库系统自动进行连接操作。
  5. 此时如果用了索引，实际反⽽会更慢
    • 块很少，表很小
  6. 没有正确的统计信息，造成CBO⽆法做出正确的选择
  • 标题: 03-索引结构、实现及使用
  • 作者: Charlie
  • 创建于 : 2024-03-11 14:03:00
  • 更新于 : 2024-07-05 12:55:04
  • 链接: https://chillcharlie357.github.io/posts/c8b35cc6/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
03-索引结构、实现及使用
  1. 1. 索引
  2. 2. 👍B Tree/B+Tree结构
  3. 3. B树查找算法
  4. 4. 👍B树的分裂
    1. 4.1. 叶节点分裂
    2. 4.2. 非叶节点分裂
  5. 5. 👍B树的合并
    1. 5.1. 叶节点合并
    2. 5.2. 非叶节点合并
  6. 6. B+树的分裂/合并
  7. 7. B树索引能做什么
  8. 8. 索引结构
  9. 9. 索引的问题
    1. 9.1. 开销
    2. 9.2. 压缩
    3. 9.3. 索引会降低查询效率吗
  10. 10. 判断索引适用性
  11. 11. 其它索引
    1. 11.1. Hash索引
      1. 11.1.1. 特点
      2. 11.1.2. Hash函数
      3. 11.1.3. Hash碰撞
    2. 11.2. 位图索引
      1. 11.2.1. 适用场景
      2. 11.2.2. 位图联结索引
    3. 11.3. 函数索引
      1. 11.3.1. 适用场景
  12. 12. 索引和外键
    1. 12.1. 同一字段，多个索引
    2. 12.2. 系统生成键
    3. 12.3. 为什么没有使用索引