大数据开发面试:索引的底层实现原理是什么?

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

索引的分类

(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.dachanpin.com/a/cyfx/10809.html

赞 (0)
程序员在写一种很新的代码,笑不活了(附源码)
上一篇 2023-05-12 02:20:26
Java开发中常用的框架有哪些?
下一篇 2023-05-12 02:21:25

相关推荐

  • 睡前场景创业,“睡不着”成就一门大生意

    帮助用户表达情感是刚需 记者接触的左儿就是青音的粉丝,从高二就开始听青音在央广的节目《神州夜航》的她告诉记者,青音的节目帮助她缓解了从高考、就业到工作抑郁等各个人生阶段的困境,“人一旦跌到谷底,就需要去外面寻找力量,每次我都会去听青音姐的节目。” 眠眠APP 快手效应迅速反导至程一的主阵地,程一电台在荔枝等平台的粉丝数量开始飙升。《终于等到你》这一期,让荔枝…

    创业分享 2023-05-21
  • 创投人谈医疗投资:在高冷领域创业如何拿投资

      本文内容来自于约印创投CEO&管理合伙人郑玉芬女士近日在清华经管创业者加速器举办的医疗大健康领域创投分享会上的精彩演讲。郑玉芬专注于医疗健康领域,她讲述了医疗投资行业的概况并作为资深投资人为创业者带来了宝贵的管理经验。   医疗投资行业概况   投/融资要把握好时间点   从整个行业角度来看,投融资最重要的在于“时间点”。就好比葡萄酒的酿造一样,…

    创业分享 2023-06-01
  • 放弃广州近百万年薪 博士夫妇来东莞创业

      11月23日10:15,松山湖引才服务办副主任袁扬波将一份“出席2017东莞高层次人才活动周启动仪式”的邀请函送到王弋手中。此前一天,市人力资源局公布了东莞市第7批15名创新创业领军人才名单,王弋位列其中。   按照东莞市现行人才政策,每名创新创业领军人才将可以获得200万~500万元的奖励与补助,让这对从广州来东莞创业的夫妇信心更加坚定。   王弋,河…

    创业分享 2023-05-21
  • 游戏打鱼机BOB体育资讯洛里26+6猛龙咬伤尼克斯6连胜 西卡23+7莫

    满月对天蝎座的影响(图) 欧洲每年至少有5500万名儿童遭受着某种形式的暴力。据联合国网站14日报道,世界卫生组织估计,在欧洲2.04亿18岁以下儿童中,有9.6%的儿童经历过性剥削,22.9%的儿童曾遭到身体虐待,29.1%的儿童受到过情感伤害。此外,每年有700名儿童被杀害。研究表明,经历暴力的儿童患精神疾病、吸毒、饮酒和肥胖风险更高,晚年患慢性疾病的风…

    创业分享 2023-05-12
  • 浙江新昌“道德银行”让有德者创业有底气

      “多亏了‘道德银行’提供的信用贷款解了我燃眉之急。”浙江省新昌县“一元爱心”之家公益组织负责人金苗华,在流动资金缺口之时,获得了“‘善行文明’道德银行”免抵押低息贷款40万元,为他的创业注入了强劲动力。   道德与信贷挂钩,这是新昌县开展新时代公民道德建设的创新举措。2018年,新昌县委宣传部、新昌县文明办和新昌农商银行联合成立绍兴市首家“‘善行文明’道…

    创业分享 2023-05-12

发表回复

登录后才能评论

联系我们

在线咨询: QQ交谈

邮件:362039258@qq.com

工作时间:周一至周五,9:30-16:30,节假日休息