什么是索引？

索引是主表上的一种辅助数据结构，对数据库表中一个或多个列的值进行排序，用于提高主表的查询速度

简述B+树索引、Hash索引及聚簇索引的实现原理和优缺点。

• B+树索引
  • 实现原理
    将索引键组织成一棵平衡树， 即从树根到树叶的所有路径一样长，数据（指向基本表记录存储位置的指针）存储在叶结点，最底层的叶节点包含每个索引键和指向被索引行的指针（行id），叶节点之间有通道可供平行查询，每一个叶节点都和磁盘页面大小一致。
  • 优点
    • 范围查询的效率更高
    • 缓存命中率高 (空间局部性原理）
    • 更新维护代价小
  • 缺点
    • 相对于Hash索引，B+树的查询速度在等值查询时可能较慢
    • 索引本身需要占用额外的存储空间
• 散列索引（Hash Index）
  • 实现原理
    根据给定索引值，用一种算法将记录分散存储到多个“桶”中（一般一个桶就是一个数据块，块中内容用一次磁盘操作就可以读取到内存中）。当要查找记录时，用相同算法算出该记录所在的桶，读取整个桶的数据到内存中，然后在桶中顺序查找要找的纪录
  • 优点
    • 等值查询非常快，因为可以直接通过哈希值定位到数据
    • 索引结构相对简单，占用空间较小
  • 缺点
    • 不支持范围查询
    • 在哈希冲突较多时，查询效率可能下降
• 聚簇索引（Cluster Index）
  • 实现原理
    数据在物理文件中的存放位置不再是无序的，而是根据索引中键值的逻辑顺序决定了表中相应行的物理顺序，即形成索引组织表
  • 优点
    • 在聚簇索引列上的查询速度比B+树索引快
    • 数据在物理上按顺序排在数据页上，重复值也排在一起，因而在使用包含范围检查(between、<、<=、>、>=)或使用group by或order by的查询时，可以大大提高查询速度
  • 缺点
    • DML频繁的表建立聚簇索引会带来大量索引数据维护的开销