风也温柔

计算机科学知识库

数据库索引数据结构 「MySQL」 - 数据库索引-下

  一、索引模型

  中,根据主键顺序以索引的形式存放,这种存储方式的表称为索引组织表数据库索引数据结构,使用了B+树索引模型,所以数据都是存储在B+树中的。每一个索引在里面对应一棵B+树。

  假设,有主键列为ID的表,表中有字段k,并且在k上有索引。

   mysql> CREATE TABLE T(

           id int PRIMARY KEY,
           k int NOT NULL,
           name varchar(16),
           index (k)

  表中R1~R5的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6),两棵树的表示如下图:

  根据叶子节点的内容,索引类型分为主键索引和非主键索引。

  主键索引的叶子节点存的是整行数据。中,主键索引也被称为聚簇索引( index)。

  非主键索引的叶子节点内容是主键的值。 里,非主键索引也被称为二级索引( index)。

  A、主键索引和普通索引

  数据库索引数据结构_数据库里索引常用的数据结构_行为数据是什么结构数据

  1、主键查询

   * from T where ID=500,只需要搜索ID这棵B+树

  2、普通索引查询

   * from T where k=5,则需要先搜索k索引树,得到ID的值为 500,再到ID索引树搜索一次,这个过程称为回表。

  也即基于非主键索引的查询需要多扫描一棵索引树,因此在应用中应尽量使用主键查询。

  B、索引维护

  B+树为了维护索引有序性,在插入新值的时候需要做必要的维护。

  插入新的行ID值为700,则只需要在R5的记录后面插入一个新记录;如果新插入的ID值为400,就相对麻烦了,需要逻辑上挪动后面的数据,空出位置。

  而更糟的情况是,如果R5所在的数据页已经满了,根据B+树的算法,这时候需要申请一个新的数据页,然后挪动部分数据过去,这个过程称为页分裂,在这种情况下,性能会受影响。

  当然有分裂就有合并,当相邻两个页由于删除了数据,会将数据页做合并,合并的过程,可以认为是分裂过程的逆过程。

  C、自增主键

  大部分数据库开发规范中都要求设置「自增主键」。

  自增主键一般是这样定义的,NOT NULL KEY 。

  插入新记录的时候可以不指定ID的值,系统会获取当前ID最大值加1作为下一条记录的ID值。

  自增主键的插入数据模式,符合递增插入的场景,每次插入一条新记录,都是追加操作,不涉及挪动其他记录,也不会触发叶子节点的分裂。

  而有业务逻辑的字段做主键,则往往不容易保证有序插入,这样写数据成本相对较高。

  除了考虑性能外,我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段,比如字符串类型的身份证号,那应该用身份证号做主键,还是用自增字段做主键呢?

  由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键,那么每个二级索引的叶子节点占用约 20 个字节,而如果用整型做主键,则只要 4 个字节,如果是长整型()则是 8 个字节。

  显然,主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。

  所以,从性能和存储空间方面考量,自增主键往往是更合理的选择。

  D、举个栗子-A

   mysql> create table T (

            ID int primary key,
            k int NOT NULL DEFAULT 0,
            s varchar(16) NOT NULL DEFAULT '',
            index k(k)
           )
           engine=InnoDB;
    

  如果执行 * from T where k 3 and 5,需要执行几次树的搜索操作,会扫描多少行?

  在k索引树上找到k=3的记录,取得ID=300;再到ID索引树查到ID=300对应的R3;在k索引树取下一个值k=5,取得ID=500;再回到ID索引树查到ID=500对应的R4;在k索引树取下一个值k=6,不满足条件,循环结束。

  因为使用非主键进行where从句查询,会对索引k进行一次搜索,再通过回表对主键进行一次搜索。

  E、覆盖索引

  如果执行的语句是 ID from T where k 3 and 5,此时只需要查ID的值,而ID的值已经在k索引树上了,因此可以直接提供查询结果,不需要回表。

  也即,索引k已经「覆盖了」查询需求,称为覆盖索引。

  由于覆盖索引可以减少树的搜索次数,显著提升查询性能,所以使用覆盖索引是一个常用的性能优化手段。

  F、举个栗子-B

  在一个市民信息表上数据库索引数据结构 「MySQL」 - 数据库索引-下,是否有必要将身份证号和名字建立联合索引?

   CREATE TABLE tuser (

      `id` int(11) NOT NULL,
    <p>![数据库索引数据结构_行为数据是什么结构数据_数据库里索引常用的数据结构][2]

      `id_card` varchar(32) DEFAULT NULL,
      `name` varchar(32) DEFAULT NULL,
      `age` int(11) DEFAULT NULL,
      `ismale` tinyint(1) DEFAULT NULL,
      PRIMARY KEY (`id`),
      KEY `id_card` (`id_card`),
      KEY `name_age` (`name`,`age`)

</p>
  身份证号是市民的唯一标识,如果有根据身份证号查询市民信息的需求,只要在身份证号字段上建立索引就够了;但如果有一个高频请求,要根据市民的身份证号查询他的姓名和年龄,那使用联合索引数据库索引数据结构,通过覆盖索引查找,不用回表整行记录,提高性能。

  G、最左前缀原则

  行为数据是什么结构数据_数据库索引数据结构_数据库里索引常用的数据结构

  B+树数据结构,可以利用索引的「最左前缀」,来定位记录。根据上图,索引项是按照索引定义里面出现的字段顺序排序的。

  当查询所有名字是张三的人,可以快速定位到ID4,然后向后遍历得到所有需要的结果。

  如果需要查询的是所有名字第一个字是张的人,会使用where name like 张 %方式查询,这种情况下,也能够用上这个索引,查找到第一个符合条件的记录是ID3,然后向后遍历,直到不满足条件为止。

  数据库里索引常用的数据结构_数据库索引数据结构_行为数据是什么结构数据

  不只是索引的全部定义,只要满足最左前缀,就可以利用索引来加速检索。

  基于上面对最左前缀索引的说明,建立联合索引时,需要合理安排索引内的字段顺序。

  索引的复用能力(如果通过调整顺序,可以少维护一个索引,那么这个顺序往往就是需要优先考虑采用的);当有了(a,b)这个联合索引后,一般就不需要单独在a上建立索引。

  如果既有联合查询,又有基于a、b各自的查询,查询条件里面只有b的语句,是无法使用(a,b)这个联合索引的,这时候还需要维护另外一个b索引。

  H、索引下推

  以市民表的联合索引(name, age)为例,检索出表中:名字第一个字是张,而且年龄是10岁的所有男孩。

  mysql> select * from tuser where name like '张%' and age=10 and ismale=1;

  除了最左前缀索引找到的张%,其他数据的匹配,还是需要比较进行处理。

  MySQL 5.6之前,只能从ID3开始一个个回表,到主键索引上找出数据行,再对比字段值;

  行为数据是什么结构数据_数据库里索引常用的数据结构_数据库索引数据结构

  MySQL 5.6引入了索引下推优化(index ),可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数

  数据库索引数据结构_数据库里索引常用的数据结构_行为数据是什么结构数据

  在(name,age)索引内部就判断了age是否等于10,对于不等于10的记录,直接判断并跳过。上图例子只需对ID4、ID5两条记录回表取数据判断,只需回表2次。

  参考:

  极客时间 -MySQL实战45讲

  文章来源:https://zhuanlan.zhihu.com/p/58293083