不管是二叉搜索树还是多路搜索树只要是搜索树那么节点的关键字必须是可以通过某种方式进行大小比较的一选择BTree的原因1.常用的搜索二叉树的平衡二叉树红黑树 等由于每个节点只能存放一个索引关键字如果数据量比较大的话就会导致树的高度很高这样在查询的过程中就有可能需要多次从磁盘加载索引的文件的中的节点数据每次加载都需要进行IO操作导致查询性能比较低2.B-Tree 是一种平衡多路搜索树每个节点可以存储多个索引关键字一个父节点可以有多个子节点(大于2个)一个N阶B-Tree每一个节点最多包含N-1个索引关键字最多有N个子节点这样本来是可以大大降低搜索树的高度但是由于B-Tree的非叶子节点中除了索引关键字还包含这些关键字所对应的行数据这样在每个节点的存储大小固定的情况下如果每一行的数据很大的话就会导致每个节点包含的索引关键字变少同样也有可能会使得树的高度比较高。B-Tree对范围查询范围查找的支持也不是太好3.BTree是在B-Tree基础上进行优化得来的一种多路搜索树BTree的非叶子节点上仅存储索引关键字组合索引存储多个字段的值不存储数据数据只存储在叶子节点上并且数据是按照顺序拍列的。BTree包含数据的叶子节点之间是通过双向列表连接的而且是按照大小顺序连接的支持正向next和反向prev查询例如ORDER BY Key DESC。非叶子节点不存放数据只存放索引关键字这样相同存储容量的非叶子节点可以存储更多的索引关键字也可以有更多的子节点所以树的高度也可以降低1. 非叶子节点的结构存储内容一组有序的索引键K1, K2, ..., Km-1。m个子节点指针P0, P1, ..., Pm其中P0指向所有键 K1的子树。P1指向K1 ≤ Key K2的子树。...Pm指向所有键≥ Km-1的子树。存储的结构非叶子节点[P0] [K110] [P1] [K220] [P2] [K330] [P3]若查找Key15会进入P1指向的子树因为10 ≤ 15 20。2. 从非叶子节点定位到叶子节点的步骤(1) 初始查找根节点从根节点开始通过二分查找定位目标Key所在的子节点指针。若根节点是叶子节点B树高度为1直接返回数据。否则找到第一个≥目标Key的索引键选择其左侧的子节点指针。(2) 递归向下搜索对选中的子节点可能是非叶子节点或叶子节点重复以下操作判断节点类型如果是非叶子节点继续二分查找定位下一个子节点指针。如果是叶子节点停止搜索从叶子节点中提取数据或确认数据不存在。移动到子节点根据选中的指针访问下一层节点。(3) 终止条件到达叶子节点时叶子节点可能包含目标数据行如数据库行记录-InnoDB的主键索引。目标数据行的主键 (InnoDB的非主键索引)指向数据的指针也就是行地址-MyISAM的主键索引和非主键索引都是若未找到目标Key则说明数据不存在。[Root: P1(K10), P2(K20), P3]/ | \[P1: K5] [P2: K15] [P3: K25] (假设非叶子节点)/ \ / \ / \[L1] [L2] [L3] [L4] [L5] [L6]查找Key15根节点10 ≤ 15 20→ 选择P2。P2节点键为15其P1指向L3假设P1是左子指针P2是右子指针。进入L3叶子节点查找Key15的记录。查找逻辑目标KeyK在非叶子节点中匹配时不会直接返回数据而是根据K的位置选择子节点指针继续向下搜索。4. 关键点非叶子节点的键是子树的“分隔符”非叶子节点的键不代表实际数据而是用于划分子树的范围。例如若非叶子节点包含键[10, 20]则P0子树的所有键 10。P1子树的所有键[10, 20)。P2子树的所有键≥ 20。总结非叶子节点的作用作为索引的“路由表”通过键值范围划分子树。定位过程从根节点开始二分查找目标Key所在的子节点指针。递归进入子节点直到到达叶子节点。关键特性非叶子节点的键是子树的分隔符不存储实际数据。所有数据最终必须通过叶子节点访问保证范围查询和顺序访问的效率。二InnoDB 和 MyISAM索引的查询顺序1.InnoDB 主键索引InnoDB的主键索引叶子节点直接存放目标数据行的数据因此InnoDB的主键索引查询的时候不用回表直接就能拿到数据行2. InnoDB 非主键索引InnoDB的非主键索引叶子节点存放的是目标数据行的主键根据二级索引查到目标数据行的主键集合然后拿着查到的主键集合再去主键索引中查目标数据行的数据也就是回一次表3. MyISAM 主键索引MyISAM主键索引存储索引的文件和存储行数据的文件是分开的MyISAM主键索引的叶子节点存的是目标行数据在数据行文件中的地址先从主键索引查到目标行的地址的集合在拿着查到的地址集合去数据行文件读取目标的数据行也算是一次回表4. MyISAM 非主键索引MyISAM非主键索引存储索引的文件和存储行数据的文件是分开的MyISAM非主键索引的叶子节点存的是目标行数据在数据行文件中的地址先从非主键索引查到目标行的地址的集合在拿着查到的地址集合去数据行文件读取目标的数据行也算是一次回表三mysql常见面试题1.如果不手动给InnoDB的表指定主键InnoDB是mysql的一种存储引擎它会为每个表创建一个主键索引如果表没有明确的指定主键索引InnoDB会使用一个隐藏的自动生成的主键来创建索引(row_id)。这个隐藏的索引使用的是BTree的结构2.hash索引只在Memory存储引擎才可以使用3.聚集索引和非聚集索引(都是使用的BTree)1.聚集索引--索引和数据存储在同一个文件中(InnoDB)2.非聚集索引--索引和数据存储在不同的文件中(MyISAM),查找的时候先在索引文件中找到要查询的key对应的数据在数据文件中的地址拿着地址去数据文件加载对应的数据4.一级索引(InnoDB主键索引) 和 二级索引 (InnoDB中除了主键索引以外的其他索引)1.一级索引的叶子节点直接存放的就是数据2.二级索引的子节点存储的是主键的值还需要拿着从二级索引中查到主键值去一级主键索引中查找对应的数据5.回表先通过二级索引找到主键的值再去主键索引中查找最终数据的过程叫做回表6.覆盖索引如果sql语句要查寻的所有字段都包含在某个索引中(也能是组合索引)这样要查询的数据在索引中就可以全部获取到就不用再去主键索引中根据主键再回表查一次这样就达到了索引覆盖可以大大提高查询效率7.索引下推在没有索引下推的情况下1.存储引擎通过索引找到符合索引条件的记录2.将这些记录的主键值返回给服务器层3.服务器层根据这些主键值回表获取完整记录4.服务器层再根据WHERE子句中的其他条件进行过滤有了索引下推后1.存储引擎不仅检查索引条件还会检查WHERE子句中能使用索引的其他条件2.只在索引层面就过滤掉不符合条件的记录减少回表操作工作原理假设有一个表users(id, name, age)在(name, age)上有联合索引执行查询SELECT * FROM users WHERE name LIKE 张% AND age 20;没有ICP时1.存储引擎只能使用name LIKE 张%条件通过索引查找2.找到所有姓张的用户后返回主键给服务器层3.服务器层回表获取完整记录再检查age 20条件有ICP时存储引擎不仅使用name LIKE 张%条件还会在索引中检查age 20条件如果age是联合索引的一部分只有同时满足两个条件的主键才会被返回给服务器层进行回表查询优势减少回表次数过滤掉更多不符合条件的记录减少I/O操作提高查询性能特别是对于非主键索引的查询降低CPU使用服务器层需要处理的数据量减关键结论单列索引的 ICP 优化有限如果 WHERE 子句中的其他条件如age 20不涉及索引列ICP 无法下推这些条件优化效果不明显。ICP 更适合组合索引组合索引中包含多个列时存储引擎可以直接在索引中检查更多条件。单列索引可以达到ICP效果的特例SELECT * FROM users WHERE name LIKE 张% AND id 100; 执行计划分析 1.存储引擎通过 idx_name 索引找到 name LIKE 张% 的记录。 2.由于 id 是主键存储引擎的索引叶子节点中包含 id 的值因此可以直接在索引层过滤 id 100。 3.最终只有满足 name LIKE 张% AND id 100 的记录才会回表。CREATE TABLE users ( id INT PRIMARY KEY, name VARCHAR(20), age INT, -- 创建虚拟列存储 age 的某种计算值 age_flag TINYINT GENERATED ALWAYS AS (age 20) STORED, KEY idx_name (name) ); -- 查询使用单列索引 idx_name并过滤虚拟列 age_flag EXPLAIN SELECT * FROM users WHERE name LIKE 张% AND age_flag 1; 执行计划分析 1.存储引擎通过 idx_name 索引找到 name LIKE 张% 的记录。 2.由于 age_flag 是存储的虚拟列其值直接存储在索引中或可通过索引快速访问因此可以下推 age_flag 1。 3.最终只有满足 name LIKE 张% AND age_flag 1 的记录才会回表。8.单列索引和组合索引1.单列索引就是只包含一个字段的索引数据的排序就是按照索引列的关键字的大小拍需2.组合索引是包含多个字段的索引数据的排序是先按照最左边的索引字段的大小排序当最左边的列的值大小相等时再按照它后面的索引列值的大小排序依次类推。注意组合索引有个最左前缀原则只要查询条件中用到了组合索引中最左边的字段那么本次查询中该组合索引就会生效至少部分生效。如果没用到最左边的字段则该组合索引完全失效。原因是构建BTree索引的时候默认是使用最左边的字段的大小进行大小比较和子节点的排序的只有在左边的节点相等的情况下才会按照右边字段的大小进行大小比较和叶子节点的排序。也就是如果不考虑左边节点的情况下只考虑右边节点其实是无序的。所以只要组合索引中左边的某个字段没用到或者边的字段使用了范围查询那么该字段后面的字段的索引也不起作用。上图中的这个组合索引是 (name, age,id) 组合索引 (就是把每一行中这三个字段的值整体看作一个关键字)默认情况下在最终构建好的索引树中只有name字段的这部分是始终有序的age这部分从整体来看是无序的只有在name相同的情况下age部分才会局部有序3.从某种角度来说创建一个组合索引相当于多个单独的索引例如创建组合索引(a,b,c) ,这种情况下只需要创建一棵索引树但是当我们的查询条件中包含a,ab,abc 的情况下都可以用到该组合索引。而且还可能利用索引下推减少回表次数提高查询效率如果查询的字段正好都包含在组合索引中形成覆盖索引那么就可以免去回表的过程效率更高。但是如果创建a , b , c 三个单列索引就需要构建三颗索引树当我们的查询条件中包含a,b 或者 a,b,c 的时候就需要遍历多颗索引树这里每遍历一颗索引树的消耗就类似于最后拿着主键集合回表一次拿着从多棵树中查询到的所有主键集合进行回表由于回表的时候主键索引中没有a,b,c这些字段也就没法进行索引下推。而且单列索引形成覆盖索引的概率也比较小。9.SQL优化1.尽量使用全值匹配2.最左前缀原则3.不能跳过组合索引中间的某个字段4.防止索引失效1.不在索引列上做计算使用函数类型转换 , 使用like xxx% not in ,not exists 这些操作会使索引失效2.在使用 , , , ! , or 这些的时候mysql内部优化器会根据检索比例表大小等整体评估是否使用索引。如果通过explain 发现 type 为allkey为空但是possible_keys不为空这就是本来可以使用索引但是mysql内部整体评估以后觉的全表扫描比使用该索引更快所以没有使用该索引。如果我们想强制使用 这个索引可以使用 force_index(索引名) 来强制使用该索引在B站上看了有人总结的一个顺口溜挺好记忆的索引使用总结:全值匹配我最爱最左前缀要遵守带头大哥不能死中间兄弟不能断;索引列上少计算范围之后全失效;Like百分写最右覆盖索引不写星;不等空值还有or索引失效要少用;VAR引号不可丢SQL高级也不难!10.Trace工具可以使用mysql提供的 trace 工具来分析mysql为什么没有使用我们想让它使用的索引