每日三思20200829

自答

索引是一种数据结构，其目的是为了提高数据查询的效率

问题1：

• 哈希表：K-V存储数据的结构，通过KEY获取查找的值VALUE，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。 如果多个值经过哈希函数计算相同的话，处理方法是拉出一个链表来记录相同哈希数据。该模型适合等值查询，其缺点因为数据不是有序的，进行范围查询的数据很慢。
• 有序数组：其优点是进行等值查询或范围查询中的性能非常优秀，但是在更新数据的时候，成本很高。例如插入一个元素，首先得找到第一个大于该元素的位置插入元素，同事需要将该元素之后的记录往后移，所以有序数组索引只适合静态存储引擎
• 二叉搜索树：查询时间复杂度为O(log(N))，更新复杂度O(log(N))。树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增

问题2：

• InnoDB表都是根据主键顺序已索引的形式存放的，存储方式被称为：索引组织表（B+ 树索引），每一个索引在InnoDB中对应一颗B+ 树
• 索引类型：
  • 主键索引（聚簇索引）：叶子节点存储的是整行数据
  • 非主键索引（二级索引）：叶子节点存储的是主键的值
    
• 两种索引类型查询的区别
  • 主键查询方式：通过主键列搜索相应的那颗B+树
  • 普通索引查询方式：先通过索引列查询索引树，得到对应的主键值，然后在通过主键找到对应的那颗B+树【称之为回表】

问题3：

• 页分裂：一般出现在插入数据时，数据页满，从而导致页分裂。缺点是性能受到影响、空间利用率降低
• 页合并：一般出现在删除了数据，导致利用率降低到一定阈值，则会触发页合并

扩展阅读：zhuanlan.zhihu.com/p/98818611