写在前面
想要做好后台开发, 终究是绕不过索引这一关的. 先问自己一个问题, InnoDB 为什么选择 B + 树作为默认索引结构. 本文主要参考 MySQL 索引背后的数据结构及算法原理和剖析 MySQL 的 InnoDB 索引.
索引
当数据量到达一定规模时, 我们通常会对经常使用的字段建立索引, 来加快数据的查询. 首先需要强调的是索引的本质是数据结构, 前辈们经过不断完善得到了几种复杂度较低并且能够降低磁盘 IO 的数据结构, 这里要说的是 B 树与 B + 树, 他们被广泛应用在文件系统与数据库系统中.
B-Tree
B 树逻辑上是一颗多叉树, 3 阶 B 树如下:
m 阶 B 树满足以下几个条件:
非叶子节点最少有 m/2 颗子树
叶子节点在同一层, 每个节点最多有 m-1 个升序排列的 key(索引列)和 m 个指针, key 与指针相互间隔
搜索二叉树的查询复杂度为 O(log2N), 而 B 树的复杂度为 O(logm/2N), 对于 N=62*1000000000 个节点, 如果度为 1024, 则 logM/2N <=4, 可以说它是效率很高的数据结构.
B + 树
B + 树是 B 树的变种, 区别有三点:
非叶子节点只存储 key, 不存储 data; 叶子节点存储所有 key 与 data, 不存储指针
叶子节点增加了顺序访问指针
每个节点最多有 m 个升序排列的 key
上述区别换来的优点包括:
非子节点可以存放更多的 key, 具有更好的空间局部性, 提高缓存命中率
叶子节点相链便于区间查找, 顺序查找替代 B 树的递归查找.
为什么选择 B + 树
首先要意识到数据检索的时间主要耗费在磁盘 IO(寻道时间, 旋转时间)上, 因此要尽量减少 IO 次数. 对树形结构的数据来说, 树的每一层代表需要一次磁盘 IO 查询, 因此设计了 "扁平" 的 B 树与更扁的 B + 树. 另外, 由著名的局部性原理, 访问的数据通常比较集中, 磁盘每次 IO 时会预读数据, 预读的长度为页 (4k) 的整数倍, B/B + 树新建节点会申请一个页的空间, 因此取一个节点只需要一次 IO(非叶子节点可存储到内存中).
MySQL 存储引擎
首先区分聚簇索引 (按主键聚集) 与非聚簇索引:
二者都使用 B + 树作为数据结构
聚簇索引的 data 存于主键索引的叶子节点中, 得到 key 同时得到 data, 非聚簇索引数据存于独立的地方, 叶节点保存的是数据的地址.
聚簇索引的辅助键索引 (非主键索引, 例如 employee 表中对 name 建索引) 叶节点存储主键而非数据(为了节省空间, 缺陷是需要到主键索引中二次查询); 非聚簇索引叶节点保存数据的地址.
聚簇索引的优势在于找到主键同时得到 data, 省去二次磁盘 IO; 另外 B + 树在插入或删除节点时周围节点地址会发生变化, 对非聚簇索引来说需要更新所有 B + 树的地址指针, 增加开销.
InnoDB
InnoDB 使用聚簇索引(MyISAM 使用非聚簇索引), 其磁盘管理逻辑单位是 Page(不同于上述内存中的页!), 每个 Page 大小为 16k, 使用 32 位 int 标识, 对应 innoDB 最大 64TB 的存储容量.
每个 Page 包括头部, 主体, 尾部三部分:
其中头部包括 id 与相邻 Page 指针(构成双向链表);
主体即 B + 树节点的存储, 其中包括很多 Record(节点)包括四类:
主索引非叶子节点: 定位 Page
主索引叶子节点: 包括 key 与该 key 对应的所有列(MySQL 表中的一行)
辅助索引非叶子节点: 定位 Page
辅助索引叶子节点: 包括索引键值与主键值(key)
主键选择
因为数据存于主索引中, 要求一个节点的各条数据记录按主键顺序存放, 当一页达到装载因子 (15/16) 会自动开辟新的页. 如果使用自增主键, 每次插入新纪录都顺序添加到索引节点的后续位置, 否则会节点中 key 会一直移动.
来源: http://www.bubuko.com/infodetail-3036144.html