Mysql——索引
索引的类型
- 按「数据结构」分类：B+tree索引、Hash索引、Full-text索引。
- 按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）。
- 按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引。
- 按「字段个数」分类：单列索引、联合索引。
Mysql索引底层数据结构
不同的存储引擎使用不同的数据结构来实现索引。
InnoDB 是 MySQL 默认的存储引擎（ 5.5 之后），使用 B+ 树（B+ Tree）来实现其索引。
使用B+树作为索引的好处
B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更“矮胖”，查询底层节点的磁盘 I/O次数会更少。
B+ 树通过分裂和合并节点来保持平衡，从而使插入和删除操作在最坏情况下的时间复杂度为 O(log n)。这种平衡机制保证了插入和删除操作的效率都比B树更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化。
B+ 树的叶子节点按顺序链接，形成了一个链表结构。这使得范围查询非常高效，因为可以从起始位置遍历到终止位置，无需回溯。Hash 在做等值查询的时候效率贼快，搜索复杂度为 O(1)。但是 Hash 表不适合做范围查询，而 B 树要实现范围查询，只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率也不如 B+ 树。