前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据库索引有哪些?

数据库索引有哪些?

原创
作者头像
王小明_HIT
修改2020-06-15 10:35:33
2.2K0
修改2020-06-15 10:35:33
举报
文章被收录于专栏:程序员奇点

数据库索引有哪些?

是否要建索引?

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

如果数据量比较少,是否使用索引对结果的影响并不大,比如数据不超过 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
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 树
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+树结构
B+树结构

总结

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

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

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数据库索引有哪些?
    • 索引的种类有哪些?
      • 聚集索引和非聚集索引区别
    • 索引原理
      • 二叉排序树
      • 平衡二叉树
      • B 树
      • B+ 树
    • 总结
    相关产品与服务
    对象存储
    对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档