一, 何为索引?
1, 索引是帮助数据库高效获取数据的排好序的数据结构.
2, 索引存储在文件中.
3, 索引建多了会影响增删改效率.
(下面这张图为计算机组成原理内容, 每查询一次索引节点, 都会进行一次磁盘 IO 读取, 即要寻道和旋转)
二, MySQL 索引结构为什么是 B + 树?
MySQL 建索引可使用的数据结构有 B + 树和 Hash 两种, 但是 Hash 用得很少, 优点是可以快速定位到某一行, 缺点是不能解决范围查询问题.
对于如果不需要使用范围查询, 只需要精准查询的场景, 可以使用 Hash 索引方法, 比如查电话号码.
再说说主流的索引方法 B + 树, 先说下为什么不用别的树结构, 再说为什么用 B + 树.
1, 为什么不用二叉树?
如果碰到下面这种单边增长的极端情况, 查找节点 4 和顺序查找没区别.(这种特殊情况的二叉树等同于链表, 时间复杂度为 O(n))
2, 为什么不用红黑树?
红黑树是一颗平衡二叉树, 数据量大的时候, 树的深度也很深, 如果树的深度有 20 层, 而查找的数据在叶子节点, 就要进行 20 次 IO 操作, 性能低.
3, 为什么不用 B 树?
B 树的特点:
叶子节点具有相同的深度
叶子节点的指针为空
叶子节点中的数据 key 从左到右递增排列
其实 B 树就是在横向做了文章, 一个节点可以存储更多数据(大节点包含很多小节点), 这样相对来说, 深度就会变浅.
提问: 横向的节点怎么查, 比如说查找上图中的节点 77?
从磁盘中把大节点查找出来, 把这个大节点加载进内存中, 节点 77 实际上是在内存中查找的, 在内存中做的是随机访问, 速度很快, 跟磁盘的寻道和旋转相比的话, 基本可以忽略不计.
提问: 为什么不可以让 B 树横向的度无限增大, 这样不就深度为 1, 查找不就更快了?(度的含义: 节点的数据存储个数)
本来是想通过一次 IO 操作把一个大节点加载进内存, 如果一个大节点的数据量太大的话, 则内存和硬盘一次交互没办法交换那么多数据, 假设一次只能交换 1 页 (4k) 的数据(有上限, 也有可能是几十页, 和计算机硬件有关), 意味着 CPU 去硬盘上做一次 IO 操作只能取 1 页的数据, 那么当一个大节点的数据量太大时, 仍要进行多次 IO 操作. 因此, 度是有上限的, MySQL 会根据计算机硬件自动进行度的优化, 一个大节点通常为 1 页空间.
4, 为什么使用 B + 树?(B + 树是 B 树的变种, 索引做了冗余, 存了多份, 但是没关系, 索引只占很小空间, 比如下图中的 15 节点)
B + 树的特点:
非叶子节点不存储 data, 只存储 key, 可以增大度(相比 B 树, B + 树的深度更浅)
叶子节点不存储指针
顺序访问指针, 提高区间访问的性能(实际上是双向指针)
提问: 为什么说 B + 树可以增大度?
因为非叶子节点只存储索引一个值, 不存储 data(B 树会存储 data), 而大节点大小是确定的, 因此节点就可以存储更多的数据, 即度可以变得更大. 这样既保证度可以达到最大, 又保证一个大节点通过一次 IO 操作可以加载进内存.(非叶子节点度更大, 深度更浅, 只有非叶子节点才影响查找次数, 叶子节点是最后一次查找, 对总的查找次数是没有影响的, 因此把 data 全部移到了叶子节点)
提问: 为什么叶子节点之间还需要用指针?(一个大节点的尾节点和下一个大节点的头节点之间的指针连接)
方便范围查询. 比如查找上图中 key>18, 如果没有指针会非常麻烦, 必须从头开始查找, 如果有指针, 则可以直接遍历 key>18 的叶子节点(链表).
B + 树索引的性能分析:
一般使用磁盘 I/O 次数评价索引结构的优劣
预读: 磁盘一般会顺序向后读取一定长度的数据 (页的整数倍) 放入内存
局部性原理: 当一个数据被用到时, 其附近的数据也通常会立马被使用
B + 树的大节点大小设为等于一个页, 每次新建大节点直接申请一个页的空间, 这能保证一个大节点物理上也存储在一个页里, 大节点载入只需一次 IO 操作
B + 树的度 d 一般会超过 100, 因此高度 h 非常小(一般为 3~5 之间)
三, MySQL 底层是怎么用 B + 树来存储数据的?
MySQL 有两种常见的存储引擎: InnoDB(默认),MyISAM(用得少, 在 MySQL8.0 中被废弃掉了), 存储引擎范围是表级别的.
1,MyISAM 索引实现(非聚集)
索引文件和数据文件是分离的
索引结构的叶子节点 value 存储的是文件指针.
.frm 是表结构文件,.MYD 是数据文件(MyISAM Data),.MYI 是索引文件(MyISAM Index).
MyISAM 主键索引查找流程: 先通过. MYI 文件找到对应索引的文件指针, 再根据文件指针去. MYD 文件中定位对应的那行数据.
MyISAM 普通索引查找流程: 和主键索引查找流程一致.
2,InnoDB 索引实现(聚集)
数据文件本身就是索引文件
表数据文件本身就是按 B + 树组织的一个索引结构文件
聚集索引的叶子节点包含了完整的数据记录
表必须有主键, 且推荐使用整型的自增主键
普通索引结构叶子节点存储的是主键值
.frm 是表结构文件,.ibd 是数据和索引文件(InnoDB Data)
InnoDB 主键索引查找流程: 通过. ibd 文件找到对应的索引, 索引的 value 即为那行对应的完整数据.
InnoDB 普通索引查找流程: 通过. ibd 文件找到对应的索引, 索引的 value 即为那行对应的主键的值, 再根据主键值去主键索引树中找到对应的行数据.
提问: 聚集索引和非聚集索引的区别?
聚集索引: 表中那行数据的索引和数据都合并在一起了.
非聚集索引: 表中那行数据的索引和数据是分开存储的.
提问: 为什么 InnoDB 表必须有主键?
因为整个数据文件本身就是按照 B + 树组织的一个索引文件, 所以必须要有主键(建 InnoDB 表时不指定主键, 默认会从表字段中选一列作为唯一主键, 如果不存在这种字段, 则后台默认生成一个长整型主键字段, MyISAM 可以没有).
提问: 为什么推荐使用整型的自增主键?
提高查询性能. 如果是使用 UUID 作为主键, 第一, UUID 长度很长, 会浪费存储空间, 第二, UUID 是字符串类型, 比较大小要查找 ASCII 码表, 查找速度没有整型 int 查找速度快, 第三, UUID 是随机生成无序的字符串, 当数据插入时, 有很大可能会导致节点位置移动, 还可能造成很多其他节点位置移动, 简单来说就是位置打乱了; 如果使用整型的自增主键, 新插入的数据都会连续的插入到磁盘的物理空间.
提问: 为什么 InnoDB 普通索引结构叶子节点存储的是主键值?(一致性和节省存储空间)
如果普通索引的 value 也存数据, 那么当往有主键索引和普通索引的表中插入数据时, 索引结构中 key 对应的 value 要存储两份数据, 增加维护成本.
单值索引: 只有一个索引, 如(id),size=1
联合索引: 多个索引合起来作为一个联合索引, 如(id,name),size>1(单值索引是联合索引 size=1 的特例)
提问: 联合索引的底层数据结构长什么样?
先比较 id, 如果 id 相等, 再比较 name, 如果 name 也相等, 则再比较 date.(索引最左前缀原理, 后面索引优化随笔会讲解)
来源: http://www.linuxidc.com/Linux/2020-02/162355.htm