jingtao8a's blog
0%

7.B+树索引

Posted on Edited on In

在没有索引的请况下：

在一个页中查找

  • 以主键为搜索条件
    可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
  • 以其它列为搜索条件
    这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。

###在很多个页中查找

分为两个步骤：
1.定位到记录所在的页
2.从所在的页内中查找相应的记录

由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚介绍过的查找方式去查找指定的记录,当然这种方法是非常耗时的

索引查找

一个简单的索引方案

  • 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值
  • 给所有页建立一个目录项，每个页对应一个目录项，每个目录项包括下面两个部分（页的用户记录中最小的主键值，我们用key来表示。页号，我们用page_no表示。）

InnoDB中的索引方案

  • InnoDB是使用页来作为管理存储空间的基本单位，也就是最多能保证16KB的连续存储空间，而随着表中记录数量的增多，需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表是不现实的。
  • 我们时常会对记录进行增删，假设我们把页28中的记录都删除了，页28也就没有存在的必要了，那意味着目录项2也就没有存在的必要了，这就需要把目录项2后的目录项都向前移动一下，这种牵一发而动全身的设计不是什么好主意～

所以InnoDB复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。
InnoDB就是通过记录头信息中的record_type来进行区分一条普通的记录是普通用户记录还是目录项记录

当为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么我们可以用下面这个图来描述它：
QQ截图20221216141803.png
一般情况下，我们用到的B+树都不会超过4层，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的Page Directory（页目录），所以在页面内也可以通过二分法实现快速定位记录

聚簇索引

我们上面介绍的B+树本身就是一个目录，或者说本身就是一个索引。它有两个特点：

1.使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：

  • 页内的记录是按照主键的大小顺序排成一个单向链表。
  • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
  • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

2.B+树的叶子节点存储的是完整的用户记录。

  • 所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

具有以上两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种索引不需要通过使用INDEX语句去创建。

二级索引（辅助索引）

上面介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。如果想以别的列作为搜索条件，可以多建立几棵B+树
在查找数据的过程中，查找完二级索引后只能获得主键值，仍然需要到聚簇索引中再查一遍，这个过程称为回表

联合索引

我们页可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，联合索引的本质上也是一个二级索引。

B+树索引注意事项

根页面万年不动窝

  • 每当为某个表创建一个B+树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录
  • 随后向表中插入用户记录时，先把用户记录存储到这个根节点中
  • 当根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新的分配页，然后再对这个新页进行页分裂的操作，根节点升级为存储目录项记录的页。

内节点中目录项记录的唯一性

一个页面最少存储2条记录

MyISAM中的索引方案

将索引和数据分开存储

  • 将表中的记录按照记录的插入顺序单独村粗在一个文件中，称之为数据文件。可以通过行号快速访问到一条记录
  • 会将索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号 的组合。先通过索引找到行号，再通过行号去找到对应的记录
  • 如果有需要的话，我们也可以对其它的列分别建立索引或者建立联合索引，原理和InnoDB中的索引差不多，不过在叶子节点处存储的是相应的列 + 行号。这些索引也全部都是二级索引。

MySQL中创建和删除索引的语句

我们可以在创建表的时候指定需要建立索引的单个列或者建立联合索引的多个列：

1
2
3
4
CREATE TALBE 表名 (
    各种列的信息 ··· , 
    [KEY|INDEX] 索引名 (需要被索引的单个列或多个列)
)
1
2
ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;