平衡二叉树是搜索效率是非常高的, 其时间复杂度是O(log(N)).
B 树索引就是在平衡二叉树基础上发展而来的.
数据页
在介绍索引之前需要先介绍下数据页,
MySQL是按数据页读取数据的, 数据页是Innodb磁盘管理的最小单位.
其结构三部分:
(1)页头: 页 ID, 指向前一页和后一页的指针, 存储的数据类型等信息, 共 38B;
(2)根据不同的数据类型, 存储不同结构的数据, 包括数据页, Undo页, 系统页, 事务数据页等;
(3)页尾: 8B
默认数据页大小是16K(16384B), 可以根据参数 innodb_page_size配置.
每个数据页会使用一个32位的int值来表示, 正好对应Innodb最大64TB的存储容量(16K * 2^32=64T)
代码语言：javascript复制mysql> show global variables = 'innodb_page_size'; -------------------------------------- ----------- | Variable_name | Value | -------------------------------------- ----------- | innodb_page_size | 16384 | -------------------------------------- ----------- B 树索引
B 树索引的节点信息也是按页存储的, 一页存储一个节点数据, 非叶子节点存储数据的范围信息, 叶子节点存储指针和数据信息(不同引擎存储的信息也不同).
MyISAM索引文件和数据文件是分离的，叶子节点仅保存数据行记录的地址(行指针).
在Innodb引擎中，分为聚集索引(主键索引)和二级索引两种。
主键索引的叶节点中保存的是索引列值和完整的数据记录(整行数据);
二级索引的叶子节点保存的是索引列值和指向主键的指针;
节点信息是以任意顺序存储在磁盘上的, 其物理位置与索引顺序的并没有对应关系. 所以读取多页数据时, 是会产生随机 IO 的; 一般来说, 磁盘每秒差不多在100次IO左右，2-3次意味着查询时间只需0.02-0.03秒;
索引查找
了解了索引的基本结构, 再看下索引是如何查找数据的.
索引查找过程是先遍历根节点信息, 找到数据的范围信息对应子节点, 一层层遍历, 最后遍历到叶子节点, 找到对应数据.
以查找数据 8 为例, 整个过程如下:
每次查找子节点都是随机IO, 可见节点存储的信息越多越好, B 树的树高也越矮越好;
这都要求索引列越小越好.
索引构建
Innodb在创建或重建索引时，是批量加载导入数据的，而不是一次插入一个索引记录的。
索引创建分为三个阶段。
1.扫描聚簇索引，生成索引数据并将添加到排序缓冲区。当排序缓冲区已满时，会将数据进行排序并写到临文件中。
2.对所有数据进行合并排序。
3.将已排序的数据插入 B 树中。在写入数据时, 页会根据配置(参数: innodb_fill_factor)保留部分空间, 为以后的数据更新和插入时使用, 减少索引调整的几率.
查询命令:
代码语言：javascript复制show variables where variable_name = 'innodb_fill_factor'索引维护
1. 索引添加数据
当索引写入新数据时, 如果页空间已经达到阈值时(根据参数innodb_fill_factor配置), 就需要重新申请一个页空间, 并将原页空间中一半的数据复制过来, 整个过程被称为页分裂.
页分裂会降低空间的利用率, 造成空间的浪费.
但如果是索引树的尾部节点, 数据页写满时会新申请一个数据页, 就不会产生页分裂的问题, 这也是主键索引选择有序自增类型的原因.
2. 索引数据删除
既然有添加, 那就会有删除操作. 当数据被delete时, 页空间也就会被释放出来了. 当达到一定阈值(配置参数MERGE_THRESHOLD)时, 就会尝试和相邻页进行合并处理, 整个过程称之为页合并.
合并阈值参数的配置方式有两种
1.表级配置
代码语言：javascript复制CREATE TABLE t1 ( id INT, KEY id_index (id) COMMENT 'MERGE_THRESHOLD=40' );2.索引级配置
代码语言：javascript复制ALTER TABLE t1 ADD KEY id_index (id) COMMENT 'MERGE_THRESHOLD=40';降低MERGE_THRESHOLD值时, 能较少的页面合并尝试次数和页面合并次数, 但设置太小可能会导致大量数据文件, 因为空页空间过多.
索引的树高
B 树的高度, 直接影响到一次查找随机 IO 的次数和索引的使用效率.
下面一起看下树高的估算.
以bigint(占 8B 空间)型主键索引为例, 指针信息占 6B, 非叶子节点可以存 16384/(8 6) = 1170个对象.
如果一行数据是 1K 大小, 那叶子节点能存储 16 条数据.
再强调下, 主键索引的叶子节点存储的是一行数据.
如此算来:
树高为2的B 树：1170 * 16 = 18720，约存1.8w条数据记录;
树高为3的B 树：1170 * 1170 * 16 = 21902400，约存2千万条数据记录。
已经创建好的索引可以通过数据字典, 查询到包括树高在内的索引信息:
代码语言：javascript复制select a.space as tbl_spaceid, a.table_id, a.name as table_name, file_format, row_format, space_type, b.index_id, b.name as index_name, page_no, b.type as index_type from information_schema.innodb_sys_tables aleft join information_schema.innodb_sys_indexes b on a.table_id = b.table_id where a.table_id = b.table_id and a.space != 0;通过这篇文章是不发现了 B 树索引的另一面了.
