索引采用的算法
索引为什么采用B+树，而不用B-树，红黑树
提升查询速度，首先要减少磁盘I/O次数，也就是要降低树的高度。
平衡二叉树、红黑树，都属于二叉树。
时间复杂度为O(n)，当表的数据量上千万时，树的深度很深，mysql读取时消耗大量 IO。
另外，InnoDB引擎采用
页为单位读取，每个节点一页，但是二叉树每个节点储存一个关键词，导致空间浪费。
B-树，非叶子节点存储数据，占用较多空间，
导致每个节点的
指针少很多，无形增加了树的深度。B+树数据都存储在叶子节点，非叶子节点只存储
健值+指针，索引树更加扁平，三层深度可以支持千万级表存储。
同时叶子节点之间通过链表关联，范围查找更快。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Michael's Blog！
相关推荐
2015-10-03
聚簇索引与非聚簇索引
在 InnoDB 里，索引B+ Tree的叶子节点存储了整行数据的是主键索引，也被称之为聚簇索引，即将数据存储与索引放到了一块，找到索引也就找到了数据。 而索引B+ Tree的叶子节点存储了主键的值的是非主键索引，也被称之为非聚簇索引、二级索引。 聚簇索引与非聚簇索引的区别： 非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键（行号） 对于InnoDB来说，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。第一次索引一般是顺序IO，回表的操作属于随机IO。需要回表的次数越多，即随机IO次数越多，我们就越倾向于使用全表扫描 。 通常情况下， 主键索引（聚簇索引）查询只会查一次，而非主键索引（非聚簇索引）需要回表查询多次。当然，如果是覆盖索引的话，查一次即可 注意：MyISAM无论主键索引还是二级索引都是非聚簇索引，而InnoDB的主键索引是聚簇索引，二级索引是非聚簇索引。我们自己建的索引基本都是非聚簇索引。 非聚簇索引一定会回表查询吗？不一定，这涉及到查询语句所要求的字段是否全部命中了索...
2017-03-20
索引的概念
索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分)， 它们包含着对数据表里所有记录的引用指针。 索引是一种数据结构。 数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。 索引的实现通常使用B树及其变种B+树。 更通俗的说，索引就相当于目录。 为了方便查找书中的内容，通过对内容建立索引形成目录。 而且索引是一个文件，它是要占据物理空间的。 MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度。 比如我们在查字典的时候，前面都有检索的拼音和偏旁、笔画等， 然后找到对应字典页码， 这样然后就打开字典的页数就可以知道我们要搜索的某一个key的全部值的信息了。
2019-05-15
覆盖索引（Covering Index）
一句话 覆盖索引 = 一个 SELECT 需要的所有字段，都能从二级索引里直接拿到，不需要回表。 EXPLAIN 显示 Using index 就是覆盖了。 一、为什么需要覆盖InnoDB 的二级索引存的是 主键值，不是数据行： 123456SELECT name FROM users WHERE age = 25;-- 走 idx_age 二级索引-- → 拿到主键 id 列表-- → 用 id 回到聚簇索引取整行 ← 这一步叫"回表"-- → 取出 name 回表 = 一次随机 IO。如果二级索引里直接就有 name，就省了这一步。 二、用联合索引覆盖12345678-- ❌ 普通索引，需要回表ALTER TABLE users ADD INDEX idx_age (age);SELECT name FROM users WHERE age = 25;-- ✅ 覆盖索引，name 直接在索引里ALTER TABLE users ADD INDEX idx_age_name (age, name);SELECT name FROM u...
2021-03-20
索引的最左前缀原则
最左前缀原则就是最左优先， 在创建多列索引时，要根据业务需求， where子句中使用最频繁的一列放在最左边。 mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配， 比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的， 如果建立(a,b,d,c)的索引则都可以用到， a,b,d的顺序可以任意调整。 =和in可以乱序， 比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序， mysql的查询优化器会帮你优化成索引可以识别的形式。 最左前缀原则可以是联合索引的的最左N个字段，也可以是字符串索引的最左的M个字符。举个例子，假如现在有一个表的原始数据如下所示： 并根据col3 ，col2的顺序建立联合索引，此时联合索引树结构如图下所示： 叶子结点中首先会根据col3的字符进行排序，若是col3相等，在col3相等的值里面再对col2进行排序，假如...
2019-05-20
索引失效的 12 种原因
一句话 索引失效 = MySQL 优化器决定不用你建的索引去执行。 永远用 EXPLAIN 验证，不要靠记忆。 12 种失效场景1. WHERE 列上做函数 / 表达式1234567-- ❌ 索引失效SELECT * FROM users WHERE YEAR(created_at) = 2024;SELECT * FROM users WHERE id + 1 = 100;-- ✅ 改写：把函数挪到右边SELECT * FROM users WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01';SELECT * FROM users WHERE id = 99; MySQL 8.0+ 支持 函数索引：ALTER TABLE users ADD INDEX idx_year ((YEAR(created_at))) 2. 隐式类型转换123456-- 字段是 VARCHAR，传了 INT-- ❌ 走全表扫SELECT * FROM...
2017-03-20
索引回表
回表 查询时一些字段值拿不到，需要到主键索引B+树再查一次。 根据索引进行条件查询，回到主键索引树进行搜索的过程 因为查询还要回表一次，再次查询主键索引树，所以实际中应该尽量避免回表的产生。 解决回表问题可以建立联合索引进行索引覆盖，如图所示根据name字段查询用户的name和sex属性出现了回表问题： 那么我们可以建立下面这个联合索引来解决： 123456create table user ( id int primary key, name varchar(20), sex varchar(5), index(name, sex)) engine = innodb; 建立了如上所示的index(name,sex)联合索引，在二级索引的叶子结点的位置就会同时也出现sex字段的值，因为能够获取到要查询的所有字段，因为就不用再回表查询一次。 强制索引 force index
评论