数据库开发-3-索引结构及使用

Lec3-索引结构及使用

1. 开发结束后才想到索引是错误的做法，应该在最开始就提出如何设计索引。
2. 如果在用的时候才创建索引会导致冗余的索引，带来计算存储资源的消耗。

1. B树索引的结构和应用

1.1. B树(B+树)的结构

1. B树索引是很多主流关系型数据库的缺省索引类型，B是平衡树索引，方框是一个块(页)。
2. B树是一块一块的将数据读取到内存，哪怕访问的是一条，也会把该条所在的块读入到内存，一般是4K一个块。
3. 为什么最开始的时候是4k一块？因为磁盘盘面转一圈是4k的存大小(1次IO操作)，是数据库查询的最大消耗。
4. 为什么B树的最底层是连接的？因为整个底层是一个顺序文件(连接的)，方便进行范围查询
5. B树结构的深度？一般深度都为3，最多深度为4
6. 索引结构是一个树状结构，块中存储一个个区间，然后每个区间用指针指向下一层节点，直到到最底层。
7. 访问上图中的一个节点：4次IO操作，3次访问索引，1次访问数据

1.2. B+树索引做什么？

1. 充分理解B+树索引的结构，你就能充分B+树能做什么不能做什么？
2. 能做的

1. 全键值 Where x = 123 (depth + 1次的固定次数)
2. 键值范围 Where 45 < x < 123 (先进行x=45，然后顺序读取直到x>=123)
3. 键前缀查找 where x LIKE J%’

3. 根据结构，请思考B+树索引不能做的有哪些?但是未必能提高

1. 等值查询：3次索引IO和1次基本表IO
2. 范围查询(1 - 100，含)：批量插入的时候索引的顺序和块的顺序是一致的，但是往往不一定会进行批量插入的(堆文件随机插入)。

1.3. 索引的另一面（问题）

1. 索引并不是因为提高磁盘查询效率而产生的数据：索引数据量一般远远大于基本表的数据量，还会涉及到双机热备等问题，索引恢复的时间大规模拉长了恢复的时间
2. 数据库是可以使用硬件等方式来弥补不足。
3. 磁盘空间的开销

1. 磁盘空间的开销、处理Oracle

1. 以创建表为例子，做查询的衰减情况如下：索引是竞争的重点。
2. 更新表数据的时候，需要修改索引，意味着大量的IO操作

2. 有触发器的数据库被称为主动数据库。

3. 数据库系统处理的开销：触发器来记录logo，过多的索引会导致锁的争用。

4. 那么不管怎么样，但，它至少能够提升查询效率不是吗?不一定
5. 思考题

1. 对于B+树索引，不少数据库都有自己的处理方式，比如，MySQL中不同的存储引擎使用了不同的方式把索引保存到磁盘上，他们会影响性能。

1. MyISAM使用前缀压缩以减少索引，而InnoDB不会压缩索引，(有啥差别? )
2. MyISAM索引按照行存储的物理位置引用被索引的行，但是InnDB按照主键值引用行，(有啥差别?)

2. 请有兴趣的同学尝试去看一下你所用数据库索引的官方参考
3. 欢迎你的思考和留言

1.4. 让索引发挥作用

1. 索引有可能降低查询效率嘛?

1. 有可能
2. 降低：

1. 如果基本表很小
2. 如果select *，则直接查询即可

2. 索引和目录

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

1. 原子粒度是直接读取记录，而不是检索大量数据而存在。
2. 索引是访问数据库的手段

3. 索引的使用是否合理，首先取决于它是否有用。
4. 判断索引适用性的依据是检索比例(retrieval ratios)
5. 什么时候应该使用B树索引：检索的结果集与整体的百分比(10%，我们一般认为10%以下是有效的)

1. 仅需要通过索引访问基本表的很少一部分行
2. 如果要处理表中的多行，可以使用索引而不使用表

6. 关系型数据库并发写困难
7. 胖表和瘦表影响了一个块中可以存放的记录个数，一般胖表支持索引的个数多于10%，而瘦表一般为5%(瘦表一个块能存储的记录个数多，导致索引的使用效果更差)

1.5. 只使用索引，不使用表

1. 复合键索引，本质上索引是按照排名第一的字段进行的索引

1.6. 让索引发挥作用

1. 索引只是查询工作的第一步
2. 读取基本表中的数据才是查询的结束
3. 同样的索引，但不同的物理结构，可能会引起查询效率的千差万别

1. 磁盘访问的速率
2. 物理I/O很可能是内存访问
3. 记录存储

4. 开发和生成环境的不同？开发生成的是连续的，但是生产中可能是不连续的

1.7. 索引无论怎么样，都是数据库的重要组成部分

1. 索引始终是数据库中极重要的组成部分

1. 通用目的或事务处理型数据库系统
2. 决策支持系统

2. 事务处理型数据库中"太多索引

1.8. 思考题

1. 既然，使用复合键索引，在select子句中，如果所有字段都在复合键索引所包括的字段之中的时候，查询可以只使用索引不使用表
2. 那么,为什么不可以针对表T (x,y;z) 这样的表，直接构建一个索引index (x,y,z) ，这样所有对这个表的访问就可以直接使用索引不使用表了，这会不会大幅度地提升查询效率呢?

2. 其他索引结构

1. 哈希索引(Hash Index)：MySQL
2. 位图索引(Bitmap Index)：Oracle
3. 位图联结索引(Bitmap join index):Oracle
4. 函数索引(function-based index)

2.1. 哈希索引

1. 哈希索引结构：所有的都是等长的数值

2. 根据结构，你能告诉我哈希索引做什么不能做什么？碰撞率的问题：一般是使用10倍的范围

1. 哈希索引只能对全键值进行查询，不支持部分键值的匹配
2. 哈希索引只支持=、in、不等于运算符
3. 没有办法对哈希索引进行排序
4. 哈希索引没有办法对原字段进行顺序查询
5. 哈希索引读取的效率高于B树索引(数值比对速度是最快的)
6. 哈希碰撞的问题

3. InnoDB有自适应哈希索引，在B树索引的某些值被频繁使用时建立自适应哈希索引。

2.2. 位图索引

1. Bitmap index, Oracle7.3引入, 位数据库仓库查询环境设计
2. 一个索引键值的条目存储指向多行的指针。
3. 位图索引可以统计null
4. 位图索引的结构

1. 每次交换都会将对应的1/0进行交换，每次锁住的是全部索引。
2. 低选择字段不要修改或尽可能小的修改。
3. 新的feature一定要看完。

5. 对于写入很不友好：会全表锁定

2.2.1. 什么是位图索引

1. 相异基数(distinct cardinality)低：字段可以取的值比较少
2. 大量临时查询的聚合

2.3. 位图联结索引(Bitmap join index)

1. 允许使用另外某个表的列对一个给定表建立索引。
2. 实际上，这就是允许对一个索引结构(而不是表本身)中的数据进行逆规范化。

2.4. MySQL怎么办？

1. MySQL没有位图索引

1. 优化替代索引组合
2. 低选择性添加特殊索引

2. Select * from profiles where sex = ‘M’ order by rating limit 10;可以添加sex，rating列上的复合索引。
3. select * from profiles where sex = ‘M’ order by rating limit 100000, 10;

1. 依旧很慢，更好的策略是限制用户查看的页数
2. 谷歌的骗人技巧，不必全部检索，有一个大概的值即可，懒加载
3. 也可以

Select * from t inner join (
  Select id from t
    Where x.sex ='m' order by rating limit 100000, 10
  )AS x USING id;

2.5. 函数索引

1. 函数索引，对F(x)的值构建索引，在通过对索引读取x所指向的记录行

1. X索引，和F(x)的索引完全不一样

2. 想一想，函数索引能用在哪?

1. 不区分大小写的查询：使用函数输入(构建一个全大写的函数索引)

1. Creat index emp_upper_idx on emp(upper(ename))
2. Select * from emp where upper(name) = 'KING'

2. T、F的巨大差异下的索引：(True / False) 如何找到少量的F(函数索引：T映射到NULL，F映射到非空，然后对该函数建立索引，建立索引的结果全为False)
3. 有选择的唯一性

1. Active的活动的名称不能相同Create unique index active_project_must_be_unique on projects(case when status = 'ACTIVE' then name end)，这样子只要有一个创建，另一个只能回滚。

2.6. 还有很多的其他索引，需要自己学习

1. 首先，现看索引的结构，从结构-能做什么-不能做什么-练习，再循环
2. 思考题

1. 请尝试，构建一个本课相似的例子(比如本课程的例子、电脑的配置的例子等等)插入大量数据，在MySQL.上，尝试用B树索引|模拟位图索引|的功能。
2. 请再想想，还有什么场景下可以使用函数索引|或者哈希索引?
3. 欢迎你在视频下留言，期待你的留言~

2.7. 索引使用的典型问题

1. 函数和类型转换对索引的影响
2. 索引和外键
3. 同一个字段，多个索引
4. 系统生成键
5. 总结，为什么没有使用我的索引？不满足优化器的条件

2.7.1. 函数和类型转换对索引的影响

1. Where f(indexed_col) = "some value"

1. 这种检索条件会使indexed_col上的索引无法发挥作用
2. 日期函数

2. 隐式类型转换(SQL往往会有隐形的函数转换)

1. name=“1234”
2. name=1234(非常常见的隐形类型转换的例子)

2.7.1.1. 字符串和日期的例子

1. B树索引只能进行前缀查询

where date_entered = to_date('18-JUN-1815', 'DD-M0N-YYYY') # 只有得到1815年6月18日0时0分的记录
where trunc(date_entered) = to_date('18-JUN-1815','DD-MON-YYYY']) # 性能问题
where date_entered >= to_date(' 18-JUN-1815', 'DD-MON-YYYY') and date_entered < to_date('19-JUN-1815', 'DD-MON-YYYY') # 区间查询解决问题

2.7.2. 索引与外键

1. 系统地对表的外键加上索引的做法非常普遍

1. 但是为什么呢?对于具有很多外键的表不合适，建立外键索引可以更快速的保证数据一致性，比如B中要删除记录，要检查A中的对应行，但如果没有则需要对A全表遍历。外键不加索引更可能会导致死锁(A加锁或B加锁)
2. 有例外吗?表B如果很少被修改，则不必要建立外键索引

2. 建立索引必须有理由：无论是对外键，或是其他字段都是如此

2.7.3. 同一字段，多个索引

1. 如果系统为外键自动增加索引，常常会导致同一字段属于多个索引的情况

1. 不需要单独为Order_id构建索引
2. 而Articles很少修改，因此也不必在Articles建立索引

2. 为每个外键建立索引，可能会导致多余索引：字段的顺序对索引很重要

2.7.4. 系统生成键

1. 系统生产序列号，远好于

1. 寻找当前最大值并加1
2. 用一个专用表保存"下一个值"且加锁更新
3. 并发性过高容易出现问题

2. 但如果插入并发性过高，在主键索引的创建操作上会发生十分严重的资源竞争。这些只能在主键索引上串行创建，大幅度降低系统并发效率。
3. 解决方案

1. 反向键索引或叫逆向索引(reverse index)：

1. 将索引字段的值反过来，比如9527变为7259
2. 使用反向键索引可以使得大概率在不同叶节点上操作，从而实现并发插入，而避开并行插入。

2. 哈希索引(hash indexing)：高并发自增我们修改为高并发的随机生成

2.7.5. 为什么没有使用我的索引?

1. 情况1:我们在使用B+树索引，而且谓词中没有使用索引的最前列：T，T(X,Y)上有索引，做SELECT * FROM T WHERE Y=5，跳跃式索引(仅CBO)
2. 情况2:使用SELECT COUNT(*) FROM T，而且T上有索引，但是优化器仍然全表扫描，所以使用count(1)
3. 情况3:对于一个有索引的列作出函数查询:Select * from t where f(indexed_col) = value
4. 情况4:隐形函数查询：隐形的过程导致没有使用索引
5. 情况5:此时如果用了索引，实际反而会更慢
6. 情况6:没有正确的统计信息，造成CBO无法做出正确的选择
7. 总结:归根到底，不使用索引的通常愿意就是"不能使用索引，使用索引会返回不正确的结果"，或者"不该使用索引，如果使用了索引就会变得更慢"

2.7.6. 总结:索引访问的不同特点

1. “查询使用了索引就万事大吉”- 误解啊 ~~
2. 索引只是访问数据的一种方式
3. "通过索引定位记录"只是查询工作的一部分
4. 优化器有更多的选择权利
5. 总结:索引不是万灵药。充分理解要处理的数据，做出合理的判断，才能获得高效方案

2.8. 思考题

1. 请研究你手上使用的数据库，比如，MySQL or Oracle, 请研究数据库管理系统提供的其它索引形式，并阅读相关的文档