05-索引与算法.md

1. InnoDB索引概述
   1. 常见索引：B+ 树索引；全文索引；哈希索引
      1. 哈希索引：自适应的索引，根据表的使用情况自动创建，不能人为干预
      2. B+ 树索引：结构类似于二叉树，根据键值快速找到 。
   2. B+ 树索引并非根据键值直接找到行，而是根据找到行所在的页，再把页加载到内存中，从内存中查找
2. 平衡二叉树
3. B+ 树
   1. 新增：B+树总是保持平衡，但是为了避免页的拆分，在Leaf Page已满时，先将记录平移到兄弟节点再做旋转操作
   2. 删除
4. B+ 树索引
   1. 高度为2-4层，查找某行记录最多只需要2-4次IO
   2. 聚集索引：叶子节点包含行数据
   3. 非聚集索引：叶子节点不包含行数据，包含聚集索引信息
   4. 索引的分裂：todo
   5. 索引管理
      1. 主键索引的添加或删除操作过程：
         1. 创建临时表，表结构为ALTER TABLE新定义的结构
         2. 导入原表数据到临时表
         3. 删除原表
         4. 临时表重命名为原表 缺点：对于大表的删除和添加操作需要很长时间，若有大量事务需要访问正在修改的表，导致数据库不可用
      2. Fast Index Creation（快速创建索引）
         1. InnoDB 1.0.x开始支持
         2. 对辅助索引创建，添加S锁，在创建过程中不需要另外创建表，速度快，数据库可用性也得到提高
         3. 删除辅助索引只需要更新内部视图，并将辅助索引的空间标记为可用，同时删除MySQL数据库内部视图上对该表的索引定义引用
         4. 因为加了S锁，所有只能进行读操作
         5. 只针对辅助索引
      3. Online DDL
         1. MySQL 5.6后支持
         2. 允许辅助索引创建的同时，进行INSERT,UPDATE,DELETE这类DML操作
         3. 支持操作
            • 辅助索引的创建和删除
            • 改变自增长值
            • 添加或删除外键约束
            • 列的重命名
         4. 原理：将DML操作日志写入到一个缓存中，完成索引创建后，通过重做日志达到数据库的最终一致性。所占用的缓存空间通过参数innodb_online_alter_log_max_size控制，默认128MB
      4. Cardinality(基数)
         1. 表示索引中不重复记录数量的预估值，该值越高说明使用该索引查询性能越高
         2. 判断选择哪个索引查询更高效，是通过分析Cardinality实现
         3. 更新Cardinality信息策略：
            1. 表中1/16的数据已发生过变化
            2. stat_modified_counter(单行更新次数)>2000000000
         4. Cardinality信息的统计和更新操作通过采样获取。
            • 取得B+树中叶子节点的数量记为A
            • 随机取B+树索引中的8个叶子节点(Leaf Page)，统计不同记录个数，即为P1,P2,...,P8
            • 根据采样信息得出Cardinality的预估值为（P1+P2+...+P8）*A/8
      5. 联合索引
      6. 覆盖索引
         1. 防止回表，通过辅助索引就能得到所有信息，无需再通过聚集索引再次执行IO操作