1 索引基础
- 索引的原理
- 减少定位记录时所经历的中间过程, 从而加快存取速度.
- 一般来说,索引本身也很大, 不可能全部存储在内存中, 因此索引往往以索引文件的方式存储在硬盘上. 这样, 索引查找过程中会产生磁盘I/O消耗.
- 评价索引的数据结构的指标: 查找过程中磁盘I/O操作次数的渐进复杂度.
- 索引的"三星系统"
- 一星: 索引将相关的记录放到一起.
- 二星: 索引中的数据顺序和查找中的排序顺序一致
- 三星: 索引中的列包含了查询中需要的全部列.
- 索引的优点
- 减少了服务器需要扫描的数据量. (索引存储了实际的列值).
- 避免排序和临时表. (按照顺序存储数据).
- 将随机I/O变为顺序I/O. (顺序存储).
- MySQL 中的索引
- 在存储引擎层实现的, 所以没有统一的索引标准.
- MYSql 不能将过滤条件传到存储引擎层.
2 B-Tree 索引
2.1 B-Tree 索引
- 所有的值按照顺序存储的, 每个叶子页到根的距离相同.
- 数据库将一个node的大小设置为一个页的大小. 每个node 只需一次I/O就可以完全载入.
- 同时, 把B-Tree中的m值设置的非常大, 从而降低了树的高度, 有利于一次完全载入.
- 索引对多个值进行排序的�依据是定义索引时的顺序.
- 适用于全键值, 键值范围, 匹配最左前缀, 匹配列前缀, 只访问索引的查询.
- 还可用于查询中的Order by 操作.
2.2 m-way 查找树
- 每个节点的键值数小于m.
- 每个节点的度(子树的数目)小于等于m.
- 键值按顺序排列.
- 子树的键值要完全小于(左树)或大于(右树)或介于父节点之间(中间树)的键值.
2.3 限制. 索引的顺序是非常重要的.
- 不是按照索引的最左列开始查找,则无法使用索引.
- 不能跳过索引中的列(�例如使用3个列做索引, 然后按1,3列进行查询).
- 若查询中有某个列的范围查询, 则其右边的所有列都无法使用索引来优化查询.
3 哈希索引
3.1 哈希索引
- 只有精确匹配索引所有列的查询才有效.
- 只有Memory引擎显式支持(非唯一)哈希索引.
- InnoDB 会在某些索引值被频繁使用时, 在内在基于B-Tree之上再创建哈希索引, 单这是完全自动,内部的行为. 用户无法控制.
- 适合: "星型"schema,需要关联很多查找表.
3.2 限制
- 哈希索引只包含哈希值和行指针,而不存储字段值. 所以不能避免行读取.
- 数据不是按照索引值顺序存储的, 也就无法用于排序.
- 不支持部分索引列匹配查找. 使用的是全部索引列的内容计算的哈希值.
- 只支持等值比较查找,而不支持任何范围查询.
- 遇到哈希冲突时, 需要遍历链表中所有的行指针, 逐行比较,知道找到所有符合条件的行.
- 若果哈希冲突很多, 那么索引维护操作的代价也会很高.
3.3 创建自定义哈希索引
- 在B-Tree基础上创建一个伪哈希索引.
- 还是使用B-Tree进行查询, 但使用哈希值而不是键本身进行索引查找.
- 在查询的Where 条件中手动指定使用的哈希函数.
- 缺陷是需要维护哈希值, 可以手动维护, 也可以使用触发器.
- 使用CRC32(), 在数据表非常大时,会出现大量的冲突,可以自实现一个64位(返回整数的)哈希函数.
- SHA1(),MD5()的设计目标是最大限度消除冲突, 所以会产生非常长的字符串,浪费空间.
- 由于"生日悖论",出现哈希冲突的概率的增长速度比想象的要快很多.
- 要避免冲突, 必须在where条件中带入哈希值和对应的值
where crc=CRC32('gun') and word = 'gnu'.
4 索引即数据结构
- 每种查找算法都只能应用于特定的数据结构之上.
- 数据本身的组织结构不可能完全满足各种数据结构.
- 索引是数据结构.
- B+ Tree: 内节点不存储数据, 只存储key; 叶子节点不存储指针.
- 每个节点的指针上线为2d.
- 磁盘预读的长度一般为页(page)的整数倍.
- 主存和硬盘以页为单位交换数据.
- 将tree 中一个节点的大小设置为一个页的大小.
- B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）.
