索引上(4)

database

索引

作用:提高数据查询的效率

常用索引模型

  • 哈希表
  • 有序数组
  • 搜索树

哈希表

以键值对的形式存储,适合于只有等值查询的场景。

用一个哈希函数把key换算成一个确定的位置,然后把value这个位置的数组中。一个key会对应一个数组,数组中会有多个valuevalue并不是有序的。

查找时先通过哈希函数算出key,找到具体的数组,然后遍历数组,找到具体的位置。

有序数组

以有序数组形式存储,等值查询和范围查询场景中性能非常优秀,只适用于静态存储引擎。

仅仅看查询效率,有序数组就是最好的数据结构了,但是,在需要更新数据多的时候就麻烦了,你往中间插入一个记录就必须得挪动后面所有的记录,成本太高。

所以,有序数组索引只适用于静态存储引擎,比如你要保存2017年某个城市的所有人口信息,这类不会再修改的数据。

搜索树

以类似二叉树的多叉树来实现。

  • 二叉搜索树:每个节点的左儿子小于父节点,父节点又小于右儿子。
  • 多叉树:每个节点有多个儿子,儿子之间的大小保证从左到右。

MySQL中,索引是在存储引擎层实现的,所有并没有同一的索引标准,即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引,其底层的实现也可能不同。

InnoDB使用了B+树索引模型,所有的数据都是存储在B+树中的。每一个索引在InnoDB里面对应一棵B+树,主键索引对应主B+树。

  • 主键索引:对应主B+树,叶子节点存储的是整行数据,也称为聚簇索引
  • 非主键索引:每个非主键索引对应一个B+树,叶子节点存储的是主键的值,也称为二级索引。

基于主键索引和普通索引的查询的区别?

  • 如果语句是select * from T where ID = 500,主键查询方式,即只需要搜索ID这棵B+树,叶子节点中有存储整行数据;
  • 如果语句是select * from T where k = 5,普通索引查询方式,则需要先搜索k索引树,得到主键ID的值为500,再到主键ID索引树搜索一次,这个过程成为回表。

回到主键索引树搜索的过程,我们称为回表。

也就是说:基于非主键索引的查询需要多扫描一颗索引树。

以上是 索引上(4) 的全部内容, 来源链接: utcz.com/z/532893.html

回到顶部