索引

很多人会有一个误区,在一个软件开发完之后,等到发现这个软件运行地较慢时,才去添加索引,这就是一个错误的观点。因为如果当一个软件上线之后,发现运行速度很慢,这种“慢”可能并不是绝对意义上的很长时间,但即使某一条SQL语句只卡顿2~3秒,也会严重影响用户的体验。一旦这个问题出现以后,如果你再去“亡羊补牢”,就会发现并不一定是数据库结构带来的问题,当你将其他问题一一排除,并确定是由于SQL语句引起的,可能已经过去了很长时间。此外很多负责运维的人并不擅长分析SQL语句。

那么,究竟应该如何正确看待索引呢?

第一, 最好是在程序准备上线时,就提前考虑好索引的问题,分析有哪些功能是用户可能频繁使用到的,给这部分加上索引

索引并不是加的越多越好,诚然如果你给所有字段都加上索引,那么查询所有字段的速度都会相应提升,可是如果你真的这么做了,即使你进行一个非常简单的“写”操作,都意味着硬盘上的索引结构要重新变化,可能带来非常多的IO行为。

二、索引的数据结构

尽管为数据建立索引与为书籍建立目录十分类似,但两者也略有不同,不同的地方在于索引的创建分为两步

第一步,以索引字段作为键,与数据进行对应,

第二步,以键为基础,构造B+树

我们之前提到过,MySQL使用的默认存储引擎是InnoDB引擎,而InnoDB存储引擎中创建的是B+树结构的索引,那么问题来了,究竟什么是B+树结构的索引?

在介绍B+树索引结构之前,我们再引入一个例子来帮助更好地理解索引,比如你过年回家要买火车票,全国的火车票就相当于表中的一行行记录,如果要你直接查询具体回家的那一趟列车,由于全国有那么多趟列车,很明显无异于大海捞针,那你会怎么去查询?

你可以先搜索出发地,目的地,这样就可以筛选出一部分记录,范围就缩小了,然后再搜索具体的时间段,范围又进一步缩小了。于是你可以不断地缩小范围,这样就可以大大提高查询效率。而火车站规定筛选的这些条件其实就相当于索引。

现在我们来看下B+树的发展历程。

B+树是由二叉查找树,平衡二叉树,B树一步步发展而来,下面我们就介绍一下B+树的发展历史

*二叉查找树*

在上图的user表中,最初数据是杂乱无章地进行排列的,现在,我要将这张表变为二叉树结构,那如何操作呢?

第一步,我们首先要给它加上索引,假设我们以ID字段的值作为基础给它创建索引,比如第一条记录的id是10,我们就将它作为key取出,和后面的名字作为value一一对应,当我们依次将所有的记录都进行一遍类似的提取操作后,提炼完以后的表就相当于每一个key都对应一条记录。

第二步,我们可以以这个key值的大小作为依据,对整张表进行排序,放入类似于上图中右边的二叉树结构。在这张图里,每一个圆圈我们称之为一个节点,其中没有子节点的我们称之为叶子节点,处于最上层的节点我们称为根节点,而位于中间的都称之为树枝。很容易发现,*二叉查找树任何节点的左子节点的键值都小于当前节点的键值,右子节点的键值都大于当前节点的键值。*

上图中,如果我们想查询id为8的数据,如果不使用索引,我们要按顺序遍历,第五次能查询到数据,但如果使用二叉树索引,因为8比10小,我们直接可以定位到左边的树枝,而到了第二层,由于8比7大,我们又可以定位到右边的分支,最后在第三层找到了我们需要的数据,一共需要查找3次。更重要的是,在这张表中,无论你要查询什么数据,由于树的结构一共只有3层,所以最多只需要3次查询就能找到。这里的3层我们称之为二叉树的高度,很明显,二叉树的高度就是所需要查到的数据的最大IO次数

*平衡二叉树*

然而根据二叉查找树的特点,上图也可以称之为二叉查找树,可是这种二叉查找树的高度很高,根本无法达到减少IO次数的目的,于是我们引进了一个新的概念——平衡二叉树。平衡二叉树的特点是\每个节点的左右子树的高度差不能超过******1。****可是平衡二叉树的数据结构也会有一定的问题,以上图中的模型为例,我们创建索引时要将索引的键值对写入硬盘,然后每次IO读取一个节点的数据,放入内存,这样固然能提速,但就好比开卡车运货,为什么我们每辆卡车只放一个很小的货物呢?

*B树*

很容易想到,我们从硬盘往内存读取数据,读取的是一个磁盘块,或者叫数据库中的一页数据。于是我们又过渡到了下一个阶段,B树。B树是在平衡二叉树的基础上,引入了磁盘块的概念,在一个磁盘块中放入较多的节点。在B树的每一页中,引入了一个指针的概念,比如在上图中,根页根据不同的范围划分,用指针指向一个分枝,进一步提升了查询的效率。然而B树仍存在一些问题,B树每一页中的节点既存放key,又存放对应的记录,这意味着每个节点都要占用较大的空间,也就是说每页只能存放较少的节点,这样在存放同等数据量的情况下,树的高度会偏高,有没有办法进一步降低树的高度呢?

B+树

B+树可以看作是在B树的基础上,非叶子节点不存储数据而只存放key,只有叶子节点才存储key和记录的值,这样,每个节点就能存储更多的键值,进一步降低树的高度。此外,B+树的叶子节点之间也有指针指向,是有序排列的,这意味着B+树在排序操作中和有天然的优势,此外在范围查询中,一旦匹配到某个叶子节点,就可以直接按顺序去找其它的叶子节点,不必再一次从树根查起,这些优点使查找的效率得到大幅提升。

三、索引的分类与区别

1、hash 索引

111

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇

You cannot copy content of this page