专栏首页程序员开发者社区数据库索引有哪些?
原创

数据库索引有哪些?

数据库索引有哪些?

是否要建索引?

索引主要是帮助数据库系统高效获取数据的数据结构。

如果数据量比较少,是否使用索引对结果的影响并不大,比如数据不超过 1000 行,那么可以不建索引。

索引的种类有哪些?

按照逻辑功能上分,有普通索引,唯一索引,主键索引,全文索引。

  • 普通索引是基础的索引,没有任何约束,主要用于提高查询效率。
  • 唯一索引主要在普通索引的基础上,增加了唯一性的约束。
  • 主键索引在唯一索引上增加了不为空的约束,也就是说 NOT NULL +Unique ,一张表中最多只有一个主键索引。
  • 全文索引,使用的并不多,MySQl 自带的全文索引只支持英文,通常采用专门的搜索引擎,比如 ES 和 Solar

按照物理实现方式,索引可以分2种:聚集索引和非聚集索引。

  • 聚集索引可以按照主键来排序存储数据,这样在查找行的时候非常有效率。主要因为聚集索引存储的是整行数据,避免回表,二次查找。主键索引就是聚集索引。每个表只能有一个聚集索引。
  • 非聚集索引,数据库会有单独的空间存放非聚集索引,这些索引项是按照顺序存储的,但是索引项指向的内容是随机存储的。系统查找数据时会进行两次查找,先找到索引,然后根据索引找到索引对应位置的数据行。

聚集索引和非聚集索引区别

  1. 聚集索引的叶子节点存储的是数据记录,非聚集索引存储的数据位置,非聚集索引不会影响数据表的物理存储顺序。
  2. 一个表只能有一个聚集索引,但是可以有多个非聚集索引。
  3. 聚集索引查询效率高,但是对数据插入,删除,更新等操作,比非聚集索引效率低。

索引原理

索引常见的模型有:哈希表、二叉排序树、平衡二叉树、B树、B+树。

二叉排序树

二叉排序树的特点是:每个节点的左儿子小于父节点,父节点又小于右儿子。

二叉排序树搜索 key 过程:

  • 如果 key 大于根节点,则从有右子树查找。
  • 如果 key 小于根节点,则在左子树进行查找。
  • 如果等于根节点 那么就返回即可。
二叉排序树

二叉排序树最大的问题是可能出现二叉树的深度大的问题。,如果一个是二叉树 按照 【 5 22 23 24 34 77 89 91】 这个顺序创造二叉排序树,那么树的深度会非常高。

二叉排序树

这样的二叉树就变成了一个类似链表的超过,时间复杂度不再是 O(logN) 而是 O(N) , 因此便有了平衡二叉树。

平衡二叉树

平衡二叉树的特点: 平衡二叉树的特点是左子树和右子树的高度不能超过1,也就是说,左子树和右子树也是平衡二叉树。

这样就可以保证二叉树搜索时间复杂度是O(logN)。

平衡二叉树

但是由于是二叉树,随着数据量变大,树还是会非常高的,但是如果是 M 叉数,数的高度会降低,于是有了 B 数。

B 树

B 树也叫 Balance Tree ,也称为平衡的多路搜索树。

B 树的特点:

  • 叶节点具有相同深度,叶节点指正为空
  • 所有索引元素不重复
  • 节点中数据索引从左到右依次递增。

B 树结构:

image

B 树的查找过程如下:比如要查找关键字 9

  1. 我们与根节点的关键字(17,35)进行比较,9小于17那么得到指针P1;
  2. 按照指针P1找到磁盘块2,关键字为(8,12),因为9在8和12之间,所以我们得到指针P
  3. 按照指针P找到磁盘块6,关键字为(9,10),然后我们找到了关键字9

B+ 树

B+ 树是在 B 树上的改进。

B+ 树的特点:

  • 非叶子节点不存储数据,只存储索引(冗余)和指针,这样就可以存放更多的索引,树高度可以降低。
  • 叶子节点包含索引字段
  • 叶子节点比 B 树增加了指针连接。
  • 叶子节点有双向指针连接(首位节点可通过指针连接)提供区间访问性能,范围查找。

B+树结构如下:

B 树

比如,我们想要查找关键字16,查找过程如下:

  1. 与根节点的关键字(1,18,35)进行比较,16在1和18之间,得到指针P1(指向磁盘块2)
  2. 找到磁盘块2,关键字为(1,8,14),因为16大于14,所以得到指针P3(指向磁盘块7)
  3. 找到磁盘块7,关键字为(14,16,17),然后我们找到了关键字16,所以可以找到关键字16所对应的数据

B+树比B树 更加矮胖,因为叶子节点不存储数据,因此能够存储更多的索引,阶数更大,深度更低,和磁盘 IO 的交互更少,查询效率也更快。并且, B+ 树在叶子节点上,通过有序链表,方便范围查找。

MySQL 把页作为存储空间的基本单位,一个页大小一般是 16 KB 。

页结构如下:

页结构

B+树结构:

B+树结构

总结

要提升索引性能,主要是减少磁盘 IO 交互的次数,因此可以使用多叉树,让树形结构变得矮胖,减少磁盘交互。在页大小相同的情况下 B+ 树非叶子节点不存储数据,因此能有更多阶,树变得更加矮胖,磁盘交互即可减少,提升索引性能。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 怎么给字符串加索引

    如果 email 不建索引,那么就只能全表扫描,如果 email 这个字段是哪个没有索引,那么这个语句只能做全表扫描。

    王小明_HIT
  • MongoDB 索引

    当往一个集合中插入多个文档后,每个文档经过存储殷引擎后,有一个位置信息,通过这个位置信息。就能从存储引擎中读出该文档。在 mmapv1 引擎下,位置信息是【文件...

    王小明_HIT
  • 数据库索引原理

    在下面这个表T中,如果我执行 select* from t where k between3and5,需要执行几次树的搜索操作,会扫描多少行?

    王小明_HIT
  • MySQL从删库到跑路_高级(六)——索引

    索引(Index)是帮助MySQL高效获取数据的数据结构。 在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的。MyISAM和In...

    良月柒
  • SQL Server之索引解析(二)

    聚集索引表由根节点(Root Node)、中间节点(Branch Nodes)、叶子节点组成。

    Edison.Ma
  • mysql索引的类型和优缺点

    现在来介绍了数据库索引,及其优、缺点。针对MySQL索引的特点、应用进行了详细的描述。分析了如何避免MySQL无法使用,如何使用EXPLAIN分析查询语句,如何...

    wangxl
  • Class文件访问标志&类索引

    在常量池以后,紧接着是2个字节的访问标志,用来表示一个Class文件的基本访问信息,包括Class是类还是接口,是否被定义为public类型,是否被定义为abs...

    shysh95
  • MySQL进阶篇(02):索引体系划分,B-Tree结构说明

    首先要明确索引是什么:索引是一种数据结构,数据结构是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合,例如:链表,堆栈,队列,二叉...

    知了一笑
  • 面试技巧,如何通过索引说数据库优化能力,内容来自Java web轻量级开发面试教程

           如果我们需要招个Java方面的高级程序员,一方面看年限(本科3年),具体到数据库方面的技能要求,包括如下三个方面:        第一,是否会...

    用户1153489
  • mysql索引使用技巧及注意事项

    一.索引的作用       一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,遇到最多的,也是最容易出问题的,还是一些复杂...

    猿人谷

扫码关注云+社区

领取腾讯云代金券