看了很多关于索引的博客, 讲的大同小异. 但是始终没有让我明白关于索引的一些概念, 如 B-Tree 索引, Hash 索引, 唯一索引.... 或许有很多人和我一样, 没搞清楚概念就开始研究 B-Tree,B+Tree 等结构, 导致在面试的时候答非所问!
索引是什么?
索引是帮助 MySQL 高效获取数据的数据结构.
索引能干什么?
提高数据查询的效率.
索引: 排好序的快速查找数据结构! 索引会影响 where 后面的查找, 和 order by 后面的排序.
一, 索引的分类
1从存储结构上来划分: BTree 索引(B-Tree 或 B+Tree 索引),Hash 索引, full-test 全文索引, R-Tree 索引.
2从应用层次来分: 普通索引, 唯一索引, 复合索引
3根据中数据的物理顺序与键值的逻辑 (索引) 顺序关系: 聚集索引, 非聚集索引.
1中所描述的是索引存储时保存的形式, 2是索引使用过程中进行的分类, 两者是不同层次上的划分. 不过平时讲的索引类型一般是指在应用层次的划分.
就像手机分类: 安卓手机, IOS 手机 与 华为手机, 苹果手机, OPPO 手机一样.
普通索引: 即一个索引只包含单个列, 一个表可以有多个单列索引
唯一索引: 索引列的值必须唯一, 但允许有空值
复合索引: 即一个索引包含多个列
二, 索引的底层实现(单值索引)
mysql 默认存储引擎 innodb 只显式支持 B-Tree( 从技术上来说是 B+Tree)索引, 对于频繁访问的表, innodb 会透明建立自适应 hash 索引, 即在 B 树索引基础上建立 hash 索引, 可以显著提高查找效率, 对于客户端是透明的, 不可控制的, 隐式的.
不谈存储引擎, 只讨论实现
Hash 索引
基于哈希表实现, 只有精确匹配索引所有列的查询才有效, 对于每一行数据, 存储引擎都会对所有的索引列计算一个哈希码(hash code), 并且 Hash 索引将所有的哈希码存储在索引中, 同时在索引表中保存指向每个数据行的指针.
B-Tree 索引(MySQL 使用 B+Tree)
B-Tree 能加快数据的访问速度, 因为存储引擎不再需要进行全表扫描来获取数据, 数据分布在各个节点之中.
B+Tree 索引
是 B-Tree 的改进版本, 同时也是数据库索引索引所采用的存储结构. 数据都在叶子节点上, 并且增加了顺序访问指针, 每个叶子节点都指向相邻的叶子节点的地址. 相比 B-Tree 来说, 进行范围查找时只需要查找两个节点, 进行遍历即可. 而 B-Tree 需要获取所有节点, 相比之下 B+Tree 效率更高.
结合存储引擎来讨论(一般默认使用 B+Tree)
案例: 假设有一张学生表, id 为主键
id | name | birthday |
---|---|---|
1 | Tom | 1996-01-01 |
2 | Jann | 1996-01-04 |
3 | Ray | 1996-01-08 |
4 | Michael | 1996-01-10 |
5 | Jack | 1996-01-13 |
6 | Steven | 1996-01-23 |
7 | Lily | 1996-01-25 |
在 MyISAM 引擎中的实现
在 InnoDB 中的实现
三, 问题
问: 为什么索引结构默认使用 B-Tree, 而不是 hash, 二叉树, 红黑树?
hash: 虽然可以快速定位, 但是没有顺序, IO 复杂度高.
二叉树: 树的高度不均匀, 不能自平衡, 查找效率跟数据有关(树的高度), 并且 IO 代价高.
红黑树: 树的高度随着数据量增加而增加, IO 代价高.
问: 为什么官方建议使用自增长主键作为索引.
结合 B+Tree 的特点, 自增主键是连续的, 在插入过程中尽量减少页分裂, 即使要进行页分裂, 也只会分裂很少一部分. 并且能减少数据的移动, 每次插入都是插入到最后. 总之就是减少分裂和移动的频率.
插入连续的数据:
插入非连续的数据
来源: https://www.cnblogs.com/liqiangchn/p/9060521.html