目录从二叉树到b+树b+树索引vs哈希索引innodb vs myisam概述以下是需要创建索引的常见场景，为了对比，创建测试表（a带索引、d无索引）：mysql> create table t

以下是需要创建索引的常见场景，为了对比，创建测试表（a带索引、d无索引）：

数据检索时在条件字段添加索引

聚合函数对聚合字段添加索引

对排序字段添加索引

为了防止回表添加索引

关联查询在关联字段添加索引

可以看出使用索引后，对查询速度优化提升是巨大的，数据库技术:MySQL索引是啥?不懂就问将从底层到实践搞懂mysql索引。

二叉树：

二叉树（binary tree）是指至多只有两个子节点的树形数据结构，没有父节点的节点为根节点，没有子节点的节点称为叶子节点。

二叉搜索树就是任何节点的左子节点小于当前节点键值，右子节点大于当前节点键值。

如下图的二叉搜索树，我们最多只需要 ⌈ l o g ( n ) ⌉ ⌈log(n)⌉ ⌈log(n)⌉即三次即可匹配到数据，而线性查找的话最坏情况需要 n n n次才可匹配到。

但是二叉树可能会退化成链表的情况，如下图所示，这样就相当于全部扫描了，导致效率不高，为了解决这个问题，需要确保二叉树一直保持平衡，即平衡二叉树。

平衡二叉树：

平衡二叉树（avl树）在满足二叉树特性的基础上，要求每一个节点的左右子树高度差不能超过1。它保证了树构造的一个平衡，当插入或删除数据导致不平衡时，会进行节点调整来保持平衡（具体算法略），确保查找效率。

平衡二叉树的一个节点对应一个键值和数据，我们每次查找数据就需要从磁盘中读取一个节点，也就是我们说的磁盘块，一个节点对应一个磁盘块。当存储海量数据时，树的节点会非常多，会进行很多次的磁盘i/o，查找效率仍是极低的。这就需要一个单节点能存储多个键值和数据的一种平衡树了。

b树： b树（blance tree）就是可以单节点存储多键值和数据的平衡树，每一个节点我们称之为页（page），即一页数据。每个节点存储了更多键值和数据，把键值和数据都放在一个页当中，并且每个节点拥有了更多子节点，子节点的个数一般称为阶。b树在查找数据读取磁盘的次数也就大大减少，查找效率比avl高很多。

如下图的3阶b树中，查找id=42的数据。首先在第一页里判断42键值大于39，根据指针p3找到第4页，再进行比较，小于键值45，又根据指针p1找到第9页，发现匹配有匹配的键值42，即找到相应数据。

b+树：

b+树是对b树的进一步优化。简单说就是b+树的非叶子节点是不存储数据的，仅存放键值。之所以这样做，是因为数据库中页的大小是固定的（innodb默认16kb），如果不存储数据，就可以存储更多键值，节点个数就越大，查找数据进行磁盘i/o次数进一步减少。

另外b+树的阶数是等于它的键值数量的，如果一个节点存储1000键值的话，那么只需要三层就可存储10亿数据，所以一般查找10亿数据只需两次磁盘i/o即可（妙啊）。

同时b+树叶节点的数据是按顺序进行排列的，所以b+树适合范围查找、排序查找和分组查找等（b各数据分散在节点上，相对就困难），也就是为什么mysql采用b+树索引的原因了。

聚集索引或聚簇索引（clustered index）是一种对磁盘上实际数据重新组织并按指定的一个或多个列的值排序。数据行的物理顺序与列值（一般是主键那列）的逻辑顺序相同，一个表中只能有一个聚集索引（因为只能以一种物理顺序存放）。

innodb就是用的聚集索引，它的表中的数据都会有一个主键，即使你不创建主键，innodb会选取一个unique键作为主键，如果表中连unique键都没有定义的话，innodb会为表添加一个名为row_id的隐藏列作为主键。

也就是说我们通过innodb把数据存放到b+树中，而b+树中的键值就是主键，那么在b+树中的叶子节点存储的就是表中的所有数据（即该主键对应的整行数据），数据文件和索引文件是同一个文件，找到了索引便找到了数据，所以我们称之为聚集索引。

聚集索引更新代价高。插入新行或更新主键时会强制将每个被更新的行移动到新的位置（因为要按主键排序），而移动行可能还会面临页分裂问题（即页已满），存储引擎会将该页分裂成两个页面来容纳，页分裂会占用更多磁盘空间。即索引重排，造成资源浪费。

聚集索引适合范围查询。聚集索引查询速度很快，特别适合范围检查（between、=）或group by、order by的查询。因为聚集索引找到包含第一个值的行后，后续索引值的行在物理上毗连在一起而不必进一步搜索，避免大范围扫描，大大提高查询速度。

比如查询id>=19并且id explain select * from test where a=88888; +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | extra | +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+ | 1 | simple | test | null | ref | idx_a | idx_a | 5 | const | 1 | 100.00 | null | +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------+ 1 row in set, 1 warning (0.03 sec) mysql> explain select b,c from test where b=88888; +----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | extra | +----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+ | 1 | simple | test | null | ref | idx_b_c | idx_b_c | 5 | const | 1 | 100.00 | using index | +----+-------------+-------+------------+------+---------------+---------+---------+-------+------+----------+-------------+ 1 row in set, 1 warning (0.00 sec) mysql> explain select * from test where a=(select a from test where a=88888); +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | extra | +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+ | 1 | primary | test | null | ref | idx_a | idx_a | 5 | const | 1 | 100.00 | using where | | 2 | subquery | test | null | ref | idx_a | idx_a | 5 | const | 1 | 100.00 | using index | +----+-------------+-------+------------+------+---------------+-------+---------+-------+------+----------+-------------+ 2 rows in set, 1 warning (0.00 sec)

重点看这三列即可：select_type、type、extra。

type（显示这一行的数据是关于哪张表的）

extra（解决查询的详细信息）

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容!

需要了解更多数据库技术:MySQL索引是啥?不懂就问，都可以关注数据库技术分享栏目—猴子技术宅（www.ssfiction.com）

本文来自网络收集，不代表猴子技术宅立场，如涉及侵权请点击右边联系管理员删除。

如若转载，请注明出处：https://www.ssfiction.com/sqljc/807373.html