InnoDB一棵B+树,可以存放多少行数据

发表于： 2022年8月9日 2022年8月9日
分类： MYSQL

show global status

结果如下:

show global status like "Innodb_page_size"

返回为:

Innodb_page_size 16384

单位为字节(Byte).

16384/1024=16,即为16KB

而对于Linux操作系统,其默认的文件系统的页大小为

getconf PAGE_SIZE

即4KB.

(Mac也支持该命令,且默认的Page大小也是4KB)

mysql中, 一个int类型占4个字节,对于varchar,最多可以占65532字节即64KB(最多能存纯汉字21844个),但绝大多数情况下,不会超过100Byte.

MySQL中varchar最大长度是多少？

即一般情况下,一行记录不太会超过1000Byte.

也就是说,一般一个Page能存10-20行数据

根据局部性原理, 当执行查询某条记录时,会把那一页的查出来放在内存,所以再查其相邻几行记录时,少了磁盘IO速度会快得多.

Mysql的”页”,有三个重要的结构: 页头,页目录,用户数据区

链表和数组正好相反, 链表写易读难.

页目录存放这一组的范围(即这一组记录行中,id的起始值和终点值----实际只需要记起点值,终点值即下一组的起点)

页目录这个东西,才是真正提高检索效率的东西

当这一页(16KB空间)已经放满了数据(比如放了18行),则需要新开辟一页.

写入时需要(重新)排序,这个动作任何(写入)时都会有,所以提升读效率的同时,降低了写的效率.

页头部分有两个指针,指向前一页和后一页.

当记录有几千几万行,由一个个page组成的一个链表,又会出现之前的问题.

把每一页,当做之前的每一行,再增加一个用于管理页的目录,称为目录页,被它管理的这些个页,成为数据页.

(注意区分目录页和数据页的页目录)

这就是一棵B+树(其实和学术上的纯粹B+树不完全一致)

abcde五个字段,a为主键,abcd均为int型,e为varchar类型

create index idx_t1_bcd on t1(b,c,d),

为t1表的bcd字段,创建一个联合索引,名为idx_t1_bcd

B+树的一个节点可以存多个元素

随着数据增多,其深度(或称高度)增加的不多

MySql中的”索引”,和es中的”索引”,含义不完全一样.

以上都是以主键的大小对一行行记录进行排序.

同时还是聚簇索引(或称聚集索引),即数据和索引存放在一起(上图中最底层为用户数据,其上为索引数据; 即叶子节点为用户数据,非叶子节点为索引数据).

在MySiam中,不存在聚集索引,即数据和索引是分开的. 在Innodb中,主键索引就是一个聚簇索引.

如果从上到下找,则用到了索引; 如果从左到右找,就是全表扫描.

对于非主键索引,下图黄色部分,存的实际是其对应记录的主键的值.

如果不这样的话, 如上图是”b-c-d”的联合索引,此时只能得到bcd的值. 但如果查询的是select *,如果不存黄色部分即主键的值, 是拿不到其他字段的值; 而如果有主键的值,就可以再进行一次查询,拿到整条记录的所有字段的信息(主键那个索引的每个叶子节点,即存了一行记录的全部信息, abcde 5个字段都存了)

这也就是建联合索引的意义. 所以即便where后面的是b=? and c=? and d=?,但如果前面是select *或select e,那还是无法避免回表. 如果前面是select b,c,d,则无需回表

对于Innode,完整的数据,只存在主键索引的叶子节点上面..所以但凡是select *,都少不了要去那里查

“最左匹配原则”,也称”最左前缀原则”

当除了主键索引,只还有一个’bcd’的联合索引,
如果是select * from t1 where c=1 and d=2,这时是会全表扫描,而无法走索引.(explain一下, 结果的type字段肯定是ALL)

从数学上看, 就是在一个按大小排好序的树状结构里,11*是可以确定大致范围的,而*11则不行. 这其实就是最左匹配的数学含义

B+树就是按照比较大小的规则排序而来的…

like “%123” 同理

如果是select * from t1 where b=1 and d=2,

即1*1, 其实是会走索引, 但只能确定一个范围.

explain看一下,type字段值为ref, key_len字段为5,即走了索引的字段的大小 (int型占4个字节,还有可能为null,即占5个字节,如果bcd都走了索引,这个字段的值就是15;如果只有b走了索引,这个字段的值就是5)

对于不等操作, 如

select * from t1 where a>1,

可以走索引,先按=1查找,找到之后,叶子节点之间的指针就起了作用,在=1对应的位置右侧的值都符合条件.

对于

select * from t1 where b>1,

explain之后的type字段是ALL,即没有走索引.但possible_key字段不为null,即可以走索引,但还是选了全表扫描. 这是因为虽然可以从上往下查用上索引(bcd为联合索引),但因为是select *,还得回表,而且是回表多次(有多少行符合条件的记录,就得回表那么多次)…在记录数不多时,不如全表扫描效率更高.

如果是
select b from t1 where b>1,则会走索引(range)

select * from t1 where b>5 (假设共有7行记录)

这时也是会走索引的(range), 查询优化器会做权衡,决定到底用哪一种

如果不加where条件,即如

select * from t1,

目的是找到表中所有b字段的值.

这个值在当前(这两个索引下)的表中,有两个地方有,即在bcd索引和在主键索引上.

那会从那个地方取呢?

主键索引的叶子节点存的是一行记录完整的数据,而bcd的叶子节点存的只是部分字段(即bcd)的数据,同样大小的一个page, bcd索引能存放的记录行数更多.(或者说,相同的记录数,bcd用的page更少)

explain一下,type字段为index. 前面的索引检索方式都是从上到下,这里是利用了叶子节点从左到右来扫描.

先看这样几条sql:

select 1=1 返回为1,即认为相等.

select 0='a' 返回为1,mysql认为两者相等

select 0='1' 返回为0

两个数据类型不同的值进行比较时,需要先进行类型转换.
一般都会把字符转换为数字:

如果是数字类型的字符,则会转为其对应的int型.

如果不是,比如为”abcd”,则直接会转为0..

这会引发出很多问题….

如下图,结果会是第一条记录

再创建一个索引:

select index idx_t1_e on t1(e)

对于:

select * from t1 where a = '1' // ‘1’会被转换为1,可以走索引

select * from t1 where a = 1 // 本来就可以走索引

select * from t1 where e = '1' // 本来就可以走索引

select * from t1 where e = 1 // 不会走索引..需要把字符转换为数字,需要把t1表所有的e字段的记录都转为int后,才可以执行判断..这时索引已经没有作用了…

在执行sql时需要类型转换/计算/日期格式的转换等时,如果需要对整张表的某个字段对操作,则不会走索引.

如

select * from t1 where a+1 = 2, 不会走索引(type字段为ALL),需要全表扫描(即会认为需要对所有的a都先加1)

limit

使用limit时,越取后面的会越慢,即

select * from t1 limit 0,1000

和

select * from t1 limit 10000,11000,

后者要慢的多.

因为找起点时,后者要花更多时间.

解决办法:

加一个子查询,

order by

select * from t1 order by b asc, c asc, d asc

不会走索引,而会全表扫描. 且explain的Extra字段是Using filesort(之前大多为where)

会先把bcd字段所有的记录取出来,然后在内存的buffer中进行排序.如果数据量非常大,内存不够,就需要用到文件(磁盘)做swap交换.

排序本身还是比较快的.

而如果走bcd索引,虽然已经排好序了,但是,用的是select *,需要回表…需要把这n条数据每一个主键,重新走一遍主键索引…这样还不如全表扫描再排序

如果是

select b from t1 order by b asc, c asc, d asc,

则会利用bcd索引,从左到右走一遍.explain的type字段为index

(index一般是叶子节点从左到右扫描)

如果是

select * from t1 where b=1 order by b asc, c asc, d asc,

这样回表的成本就小多了,有可能会走bcd这个索引

如果是

select * from t1 where order by b asc, c asc, d desc,

这样是用不到索引的.

mysql 8.0 正式支持降序索引(之前版本只是语法上支持)

对于如下创建索引的语句:

create index idx_t1_bcd on t1(b asc,c asc,d desc),

8.0之前,不管怎么写,底层其实都是asc(只是语法上支持,所以8.0之前创建索引时,都省略后面的asc/desc)

8.0之后,desc起作用了

所以在8.0中,如果建这样的索引create index idx_t1_bcd on t1(b asc,c asc,d desc),上面的sql是可以用到索引的

更多参考:

Backward index scan

基于一些合理的前提和假设,当B+树高度为3时,最多只能存2000多万行数据.

B+树变成4层,即多了一次磁盘IO,效率便会大幅度降低.

假设一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右.

所以(主键索引中)叶子节点的一个节点(即一个page,且为数据页),在这里认为可以放16行记录.

假设主键ID为bigint类型(长度为8字节)，而指针大小在InnoDB源码中是6字节，这样一共14字节，我们一个页(Page,在此为目录页)中能存放多少这样的(索引)单元，其实就代表有多少指针，即16384/14=1170。即一个目录Page,能存大概1170个(索引)单元.

那么可以算出一棵高度为2的B+树，能存放1170*16=18720条这样的数据记录。

根据同样原理, 可以算出一个高度为3的B+树可以存放：1170*1170*16=21902400条这样的记录。

所以在InnoDB中B+树高度一般为1-3层，就能满足千万级的数据存储。在查找数据时一次页的查找代表一次磁盘IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

“在InnoDB的表空间文件中，约定page number为3的代表主键索引的根页，而在根页偏移量为64的地方存放了该B+树的page level。如果page level为1，树高为2，page level为2，则树高为3。即B+树的高度=page level+1；”

SELECT
b.name, a.name, index_id, type, a.space, a.PAGE_NO
FROM
information_schema.INNODB_SYS_INDEXES a,
information_schema.INNODB_SYS_TABLES b
WHERE
a.table_id = b.table_id AND a.space <> 0;