(一)关于存储引擎
创建合适的索引是 SQL 性能调优中最重要的技术之一. 在学习创建索引之前, 要先了解 MySql 的架构细节, 包括在硬盘上面如何组织的, 索引和内存用法和操作方式, 以及存储引擎的差异如何影响到索引的选择.
MySQL 有很多种衍生版本, 这些衍生版本支持更多不同种类的存储引擎. 本文主要讨论三种 MySQL 引擎.
MyISAM 一种非事务性的存储引擎, 是 MySQL 5.5 之前版本默认的存储引擎.
InnoDB 最流行的事务性存储引擎, 从 5.5 版开始成为 MySQL 默认的引擎.
Memory 基于内存的, 非事务性的以及非持久性的存储引擎.
注意:
从 5.5 版本开始, MySQL 表的默认存储引擎从 MyISAM 换成 InnoDB, 将会使用户安装那些依赖默认设置或者专门为 MyISAM 编写的软件包时带来很大的影响.
(二)MySQL 索引类型
MySQL 支持在所有关系数据库表中创建主键, 唯一键, 不唯一的非主码索引等多种类型的索引. 此外 MySQL 还支持纯文本和空间索引类型.
MySQL 内置的存储引擎对各种索引技术有不同的实现方式, 包括: B - 树, B + 树, R - 树以及散列类型.
索引数据结构理论:
1.B - 树
B - 树中有两种节点类型: 索引节点和叶子节点. 叶子节点是用来存储数据的, 而索引节点则用来告诉用户存储在叶子节点中的数据顺序, 并帮助用户找到相应的数据.
B - 树的搜索, 从根节点开始, 对节点内的关键字有序进行二分查找, 如果命中则结束, 否则进入查询关键字所属范围的儿子节点, 重复. 直到所对应的儿子指针为空, 或已经是叶子节点.
B - 树是一种多路搜索树:
(1). 定义任意非叶子节点最多有 M 个儿子, 且 M>2;
(2). 根节点的儿子数为[2,M];
(3). 除根节点以外的非叶子节点的儿子数为[M/2,M];
(4). 每个节点存放至少 M/2-1(取上整)和至多 M-1 个关键字;
(5). 非叶子节点的关键字个数 = 指向儿子节点的指针的个数 - 1;
(6). 非叶子节点的关键字: k[i]<k[i+1];
(7). 非叶子节点的指针: p[1],p[2],.....,p[M]; 其中 p[1]指向的关键字小于 k[1]的子树, p[M]指向的关键字大于 K[m-1]的子树;
(8). 所有的叶子节点位于同一层;
2.B + 树
B + 树数据结构是 B - 树实现的增强版本. 尽管 B + 树支持 B - 树索引的所有特性, 它们之间最显著的不同点在于 B + 树中底层数据是根据被提及的索引列进行排序的. B + 树还通过叶子节点之间的附加引用来优化扫描性能.
B + 搜索和 B - 搜索不同, 区别是 B + 树只有达到叶子节点才命中(B - 树可以在非叶子节点命中), 其性能等价于关键字全集做一次二分搜索.
B + 树的特性:
(1)所有关键字都出现在叶子节点的链表中, 叶子节点相当于存储数据的数据层.
(2)不可能在非叶子节点上命中.
(3)非叶子节点相当于是叶子节点的索引, 叶子节点相当于数据层.
3. 散列
散列表数据结构是一种很简单的概念, 它将一种算法应用到给定值中以在底层数据存储系统中返回一个唯一的指针或位置. 散列表的优点是始终以线性时间复杂度找到需要读取的行的位置, 而不像 B - 树那样需要横跨多层节点来确定位置.
4. 通信 R - 树
R - 树数据结构支持基于数据类型对几何数据进行管理. 目前只有 MyISAM 使用 R - 树实现支持空间索引, 使用空间索引也有很多限制, 比如只支持唯一的 NOT NULL 列等.
5. 全文本
全文本结构也是一种 MySQL 采用的基本数据结构. 这种数据结构目前只有当前版本 MySQL 中的 MyISAM 存储引擎支持. 5.6 版本将要在 InnoDB 存储引擎中加入全文本功能. 全文本索引在大型系统中并没有什么实用的价值, 因为大规模系统有很多专门的文件检索产品. 所以不用在介绍.
MySQL 实现
对 B - 树, B + 树和散列等数据结构的基本概念有了一些了解之后, 我们就可以开始讨论 MySQL 通过支持它们的存储引擎如何实现不同的算法. 同时每种实现也对磁盘和内存使用情况有不同的影响, 这一点在大型数据库系统中是非常重要的考虑因素.
1.MyISAM 的 B - 树
MyISAM 存储引擎使用 B - 树数据结构来实现主码索引, 唯一索引以及非主码索引. 在 MyISAM 实现数据目录和数据库模式子目录中, 用户可以找到和每个 MySQL 表对应的. MYD 和. MYI 文件. 数据库表上定义的索引信息就存储在 MYI 文件中, 该文件的块大小是 1024 字节. 这个大小是可以通过 myisam-block-size 系统变量分配.
- $ ls -1h /var/lib/mysql/book/source_words.MY*
- -rw-rw---- 1 mysql mysql 9.2M 2015-05-07 19:08
- source_words.MYD
- -rw-rw---- 1 mysql mysql 7.8M 2015-05-07 19:08
- source_words.MYI
这些文件结构的内部格式可以从 MySQL 免费源代码中找到, 也可以查看 MySQL 内部手册.
在 MyISAM 中, 非主码索引的 B - 树结构存储索引值和一个指向主码数据的指针, 这是 MyISAM 和 InnoDB 的一个显著区别. 这一点导致了两个存储引擎的索引的不同工作方式.
MyISAM 索引是在内存的一个公共缓存中管理的, 这个缓存的大小可以通过 key_buffer_size 或者其他命名键缓存来定义. 这是根据统计和规划的表索引的大小来设定缓存大小时主要的考虑因素.
2. InnoDB 的 B + 树聚簇主码
InnoDB 存储引擎在它的主码索引 (也被称为聚簇主码) 中使用了 B + 树, 这种结构把所有数据都和对应的主码组织在一起, 并且在叶子节点这一层上添加额外的向前和向后的指针, 这样就可以更方便地进行范围扫描.
在文件系统层面, 所有 InnoDB 数据和索引信息都默认在公共 InnoDB 表空间中管理, 否则管理员就通过 innodb_data_file_path 这个变量指定文件路径. 这是一个叫 ibdatal 文件.
由于 InnoDB 用聚簇主码存储数据, 底层信息占用的磁盘空间的大小很大程度上取决于页面的填充因子. 对于按序排列的主码, InnoDB 会用 16K 页面的 15/16 作为填充因子. 对于不是按序排列的主码, 默认情况下 InnoDB 会插入初始数据的时候为每一个页面分配 50% 作为填充因子.
在改索引的实现方式中 B + 树的叶子节点上是 data 就是数据本身, key 为主键, 如果是一般索引的话, data 便会指向对应的主索引. 在 B + 树的每一个叶子节点上面增加一个指向相邻叶子节点的指针, 就形成了带有顺序访问指针的 B + 树. 其目的是提高区间访问的性能.
3.InnoDB 的 B - 树非主码
InnoDB 中的非主码索引使用了 B - 树数据结构, 但 InnoDB 中的 B - 树结构实现和 MyISAM 中并不一样. 在 InnoDB 中, 非主码索引存储的是主码的实际值. 而 MyISAM 中, 非主码索引存储的包含主码值的数据指针. 这一点很重要. 首先, 当定义很大的主码的时候, InnoDB 的非主码索引可能回更大, 随着非主码索引数量的增加, 索引之间大小差别可能会变得很大. 另一个不同点在于非主码索引当前可以包含主键的值, 并且可以不是索引必须有的部分.
4. 内存散列索引
在默认 MySQL 的引擎索引中, 只有 MEMORY 引擎支持散列数据结构, 散列结构的强度可以表示为直接键查找的简单性, 散列索引的相似度模式匹配查询比直接查询慢. 也可以为 MEMORY 引擎指定一个 B - 树索引实现.
5. 内存 B - 树索引
对于大型 MEMORY 表来说, 使用散列索引进行索引范围搜索的效率很低, B - 树索引在执行直接键查询时确实比使用默认的散列索引快. 根据 B - 树的不同深度, B - 树索引在个别操作中的确可能比散列算法快.
6.InnoDB 内部散列索引
InnoDB 存储引擎在聚簇 B + 树索引中存储主码: 但在 InnoDB 内部还是使用内存中的散列表来更高效地进行主码查询. 这个机制有 InnoDB 存储引擎来管理, 用户只能通过 innodb_adaptive_hash_index 配置项来选择是否启用这个唯一的配置选项.
来源: http://database.51cto.com/art/201809/582783.htm