索引的底层实现原理是什么?

索引存储在内存中,为服务器存储引擎为了快速找到记录的一种数据结构。索引的主要作用是加快数据查找速度,提高数据库的性能。

索引的分类

(1) 普通索引:最基本的索引,它没有任何限制。

(2) 唯一索引:与普通索引类似,不同的就是索引列的值必须唯一,但允许有空值。如果是组合索引,则列值的组合必须唯一。

(3) 主键索引:它是一种特殊的唯一索引,用于唯一标识数据表中的某一条记录,不允许有空值,一般用 primary key 来约束。

(4) 联合索引(又叫复合索引):多个字段上建立的索引,能够加速复合查询条件的检索。

(5) 全文索引:老版本 MySQL 自带的全文索引只能用于数据库引擎为 MyISAM 的数据表,新版本 MySQL 5.6 的 InnoDB 支持全文索引。默认 MySQL 不支持中文全文检索,可以通过扩展 MySQL,添加中文全文检索或为中文内容表提供一个对应的英文索引表的方式来支持中文。

1. 索引结构

索引是在Mysql的存储引擎(InnoDB,MyISAM)层中实现的, 而不是在服务层实现的. 所以每种存储引擎的索引都不一定完全相同, 也不是所有的存储引擎都支持所有的索引类型的, Mysql目前提供了以下4种索引:

B+Tree 索引: 最常见的索引类型, 大部分索引都支持B+树索引.

Hash 索引: 只有Memory引擎支持, 使用场景简单.

R-Tree索引(空间索引): 空间索引是MyISAM引擎的一个特殊索引类型, 主要地理空间数据, 使用也很少.

S-Full-text(全文索引): 全文索引也是MyISAM的一个特殊索引类型, 主要用于全文索引, InnoDB从Mysql5.6版本开始支持全文索引.

索引的底层实现原理是什么?

2. BTree结构

B+Tree是在BTree基础上进行演变的, 所以我们先来看看BTree, BTree又叫多路平衡搜索树, 一颗m叉BTree特性如下:

(1) 树中每个节点最多包含m个孩子.

(2) 除根节点与叶子节点外, 每个节点至少有[ceil(m/2)] 个孩子(ceil函数指向上取整).

(3) 若根节点不是叶子节点, 则至少有两个孩子.

(4) 每个非叶子节点由n个Key和n+1个指针组成, 其中 [ceil(m/2) -1 ] <= n <= m-1.

以5叉BTree为例, key的数量: 公式推导 [ceil(m/2) -1 ] <= n <= m-1.

所以 2 <= n <= 4, 中间节点分裂父节点,两边节点分裂.

索引的底层实现原理是什么?

3.B+Tree 结构

B+Tree为BTree的变种, B+Tree与BTree的区别:

1.B+Tree的叶子节点保存所有的key信息, 依key大小顺序排列.

2.B+Tree叶子节点元素维护了一个单项链表.

所有的非叶子节点都可以看作是key的索引部分。

索引的底层实现原理是什么?

由于B+Tree只有叶子节点保存key信息, 查询任何key都要从root走的叶子. 所以B+Tree查询效率更稳定.

Mysql中的B+Tree

MySql索引数据结构对经典的B+Tree进行了优化, 在原B+Tree的基础上, 增加了一个指向相邻叶子节点的链表指针, 就形成了带有顺序指针的B+Tree, 提高区间访问的性能.

MySql中的B+Tree索引结构示意图:

索引的底层实现原理是什么?

文章来源于:王晴儿网页设计博客 欢迎分享交流,转载请注明出处

本文来自投稿,不代表重蔚自留地立场,如若转载,请注明出处https://www.cwhello.com/262248.html

如有侵犯您的合法权益请发邮件951076433@qq.com联系删除

(0)
黑马程序员黑马程序员订阅用户
上一篇 2023年5月6日 23:40
下一篇 2023年5月6日 23:40

相关推荐

  • 我来分享python中输入列表数据。

    在Python中,列表是一种非常常见且功能强大的数据结构,列表是有序的集合,可以随时添加和删除其中的元素,我们可以将列表看做是数组的一种扩展,它允许存储不同类型的数据,如整数、浮点数、字符串等。 创建列表 …

    2024年7月22日
    00
  • 教你网站SEO优化怎么查看收录问题。

      seo与收录紧密相连,收录是排名的基础,没收录就一定没排名,采用科学的方法查询尽可能准确的网站收录情况,是我们从事seo的基本工作。怎样查询网站收录?方法多种多样,建议各种方式综合使用。  一些简单的方…

    2022年12月2日
    00
  • 我来分享索引量的变化对优化有什么影响。

    百度的索引量是百度蜘蛛抓取网站的页面数;而site指令查询到的页面只是放出去的页面,也就是所谓的百度显示已经收录的页面。一般情况,百度索引量与site查询的收录数,都会同步增长,这说明网站的权重在逐渐增加。如…

    2023年6月24日
    00
  • 我来分享站长网站查询工具。

    站长查询是网站管理员或SEO专家用来检测和分析网站在搜索引擎中表现的一种工具,它通常包括一系列不同的功能,如检查网站的索引状态、关键词排名、反向链接情况、网站速度以及其他与搜索引擎优化(SEO)相关的因素…

    2024年7月20日
    00
  • mysql_建立索引的优缺点

    建立索引的优缺点: 为什么要创建索引呢? 这是因为,创建索引可以大大提高系统的性能。  第一、通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。 第二、可以大大加快 数据的检索速度,这也是创建索引的…

    2017年10月19日
    0173
  • 利用免费工具软件操作月入过万的网赚新思路

    古人讲,工欲善其事必先利其器,任何行业想做好,都离不开趁手的工具。互联网也不例外,有了一些软件工具确实能够事倍功半。正是有了这些需求,很多人靠着互联网的这些工具翻身逆袭发财。其实很多工具都是我们耳熟…

    2018年8月22日
    0450
  • 小编教你页面索引一直下降的原因是什么。

    在做seo的过程中,我们非常清楚,没有建立索引的页面,是没办法参与排名的,而建立索引之后,又持续的丢失索引,同样对于排名是非常不利的。当你的网站开始出现掉索引量的时候,我们就需要多加思考,并提供解决方案…

    2023年6月10日
    00
  • 我来教你Oracle中快速搜索某一列的技巧。

    在Oracle数据库中,我们经常需要对某一列进行快速搜索,我们需要查找某个特定的值,或者查找满足某种条件的数据,为了提高查询效率,我们可以使用一些技巧来优化查询语句,本文将介绍一些在Oracle中快速搜索某一列…

    2024年6月20日
    00

联系我们

QQ:951076433

在线咨询:点击这里给我发消息邮件:951076433@qq.com工作时间:周一至周五,9:30-18:30,节假日休息