MySQL索引数据结构原理
二叉树 - 链表结构 - 相当于全表扫描
大于自己的值，放在右边，比自己小的放在左边
红黑树 - 二叉平衡树 - 数据量大时，树的高度不可控
B-Tree树
非叶子节点也会存储数据 没有维护双向指针
树的高度 由非叶子节点 的叶叉树来决定的
16^n^ = 2Kw
B+Tree - 多叉平衡树 B-Tree树的变种 树的高度可控
非叶子节点，作为一个冗余，不存储数据
1170 * 1170 * 16 = 2Kw
叶节点大小 16KB - 16384字节
Hash - hash运算 hashmap 桶 - 一次 I/O
hash冲突
仅支持 = 等值，不支持范围查询
主键 必须有，否则MySQL会自行选择一列作为 聚簇索引，如果没有，MySQL 会做个 隐藏的 聚簇索引
且为整型
数值存储空间要小
数值比较效率要比字符串比较高
数值自增排序，避免页分裂
ASCII值
二级索引 - 非聚簇索引
回表&跳表
联合索引(复合索引)
最左前缀原则
排好序
跳过最左字段，属于是无序的结构
MVCC 多版本 并发控制
processon.com/mindmap/5dbeda6ee4b0ece75948831d
buffer pool 缓存机制
LRU算法
脏页
分布式消息中间件 RabbitMQ 、 RocketMQ 、 Kafka
分布式存储中间件 Redis 、 MongoDB 、 FastDFS、 ElasticSearch、 ELK
分布式架构(微服务框架) Zookeeper 、 Dubbo 、ShardingSphere 、 Netty
cs.usfca.edu
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Michael's Blog！
相关推荐
2015-03-20
索引底层实现
Hash索引 基于哈希表实现，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），并且Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针。 B-Tree索引（MySQL使用B+Tree） B-Tree能加快数据的访问速度，因为存储引擎不再需要进行全表扫描来获取数据，数据分布在各个节点之中。 B+Tree索引 是B-Tree的改进版本，同时也是数据库索引索引所采用的存储结构。数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可。而B-Tree需要获取所有节点，相比之下B+Tree效率更高。 B+tree性质： n棵子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 所有的非终端结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。 B+ 树中，...
2015-10-03
聚簇索引与非聚簇索引
在 InnoDB 里，索引B+ Tree的叶子节点存储了整行数据的是主键索引，也被称之为聚簇索引，即将数据存储与索引放到了一块，找到索引也就找到了数据。 而索引B+ Tree的叶子节点存储了主键的值的是非主键索引，也被称之为非聚簇索引、二级索引。 聚簇索引与非聚簇索引的区别： 非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键（行号） 对于InnoDB来说，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。第一次索引一般是顺序IO，回表的操作属于随机IO。需要回表的次数越多，即随机IO次数越多，我们就越倾向于使用全表扫描 。 通常情况下， 主键索引（聚簇索引）查询只会查一次，而非主键索引（非聚簇索引）需要回表查询多次。当然，如果是覆盖索引的话，查一次即可 注意：MyISAM无论主键索引还是二级索引都是非聚簇索引，而InnoDB的主键索引是聚簇索引，二级索引是非聚簇索引。我们自己建的索引基本都是非聚簇索引。 非聚簇索引一定会回表查询吗？不一定，这涉及到查询语句所要求的字段是否全部命中了索...
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...
2015-03-20
前缀索引
因为可能我们索引的字段非常长，这既占内存空间，也不利于维护。所以我们就想，如果只把很长字段的前面的公共部分作为一个索引，就会产生超级加倍的效果。但是，我们需要注意，order by不支持前缀索引 。 流程是： 先计算完整列的选择性 :select count(distinct col_1)/count(1) from table_1 再计算不同前缀长度的选择性 :select count(distinct left(col_1,4))/count(1) from table_1 找到最优长度之后，创建前缀索引 :create index idx_front on table_1 (col_1(4))
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
2017-03-20
索引的概念
索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分)， 它们包含着对数据表里所有记录的引用指针。 索引是一种数据结构。 数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。 索引的实现通常使用B树及其变种B+树。 更通俗的说，索引就相当于目录。 为了方便查找书中的内容，通过对内容建立索引形成目录。 而且索引是一个文件，它是要占据物理空间的。 MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度。 比如我们在查字典的时候，前面都有检索的拼音和偏旁、笔画等， 然后找到对应字典页码， 这样然后就打开字典的页数就可以知道我们要搜索的某一个key的全部值的信息了。
评论
