社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  DATABASE

深入理解硬盘原理,Mysql索引底层数据结构与算法的来龙去脉(多图)

java宝典 • 5 年前 • 195 次点击  
阅读 12

深入理解硬盘原理,Mysql索引底层数据结构与算法的来龙去脉(多图)

前言:

如何触发尽量少的磁盘io 找到数据?
数据库中的索引是什么?复制代码

硬盘原理

现在大部分存储设备依然是硬盘 信息存储在硬盘里,把它拆开也看不见里面有任何东西,只有些盘片。假设,你用显微镜把盘片放大,会看见盘片表面凹凸不平,凸起的地方被磁化,凹的地方是没有被磁化;凸起的地方代表数字1(磁化为1),凹的地方代表数字0。因此硬盘可以以二进制来存储表示文字、图片等信息。

硬盘的组成

Snipaste_2020-06-29_20-41-55

一般说来,无论哪种硬盘,都是由盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等几个部份组成。

Snipaste_2020-06-29_20-43-35

所有的盘片都固定在一个旋转轴上,这个轴即盘片主轴。而所有盘片之间是绝对平行的,在每个盘片的存储面上都有一个磁头,磁头与盘片之间的距离比头发 丝的直径还小。所有的磁头连在一个磁头控制器上,由磁头控制器负责各个磁头的运动。磁头可沿盘片的半径方向动作,(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。而盘片以每分钟数千转到上万转的速度在高速旋转,这样磁头就能对盘片上的指定位置进行数据的读写操作。

由于硬盘是高精密设备,尘埃是其大敌,所以必须完全密封。

硬盘工作原理

硬盘在逻辑上被划分为磁道柱面以及扇区. Snipaste_2020-06-29_20-46-11

盘面号:扇区所在的磁头(或盘面) 柱面号:磁道,确定磁头的径向方向。 扇区号:在磁道上的位置。也叫块号。确定了数据在盘片圆圈上的位置。

访盘请求完成过程:

确定磁盘地址(柱面号,磁头号,扇区号),内存地址(源/目): 当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。

为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点: 1)首先必须找到柱面,即磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间, 2)然后目标扇区旋转到磁头下,即磁盘旋转将目标扇区旋转到磁头下。这个过程耗费的时间叫做旋转时间。 即一次访盘请求(读/写)完成过程由三个动作组成:        1)寻道(时间):磁头移动定位到指定磁道         2)旋转延迟(时间):等待指定扇区从磁头下旋转经过         3)数据传输(时间):数据在磁盘与内存之间的实际传输

因此在磁盘上读取扇区数据(一块数据)所需时间:

Ti/o=tseek +tla + n *twm
其中:
tseek 为寻道时间
tla为旋转时间
twm 为传输时间复制代码
磁盘的读写原理

系统将文件存储到磁盘上时,按柱面、磁头、扇区的方式进行,即最先是第1磁道的第一磁头下(也就是第1盘面的第一磁道)的所有扇区,然后,是同一柱面的下一磁头,……,一个柱面存储满后就推进到下一个柱面,直到把文件内容全部写入磁盘。 (文件的记录在同一盘组上存放是,应先集中放在一个柱面上,然后再顺序存放在相邻的柱面上,对应同一柱面,则应该按盘面的次序顺序存放。)从上到下,然后从外到内。数据的读/写按柱面进行,而不按盘面进行,先) 系统也以相同的顺序读出数据。读出数据时通过告诉磁盘控制器要读出扇区所在的柱面号、磁头号和扇区号(物理地址的三个组成部分)进行。磁盘控制器则 直接使磁头部件步进到相应的柱面,选通相应的磁头,等待要求的扇区移动到磁头下。在扇区到来时,磁盘控制器读出每个扇区的头标,把这些头标中的地址信息与期待检出的磁头和柱面号做比较(即寻道),然后,寻找要求的扇区号。待磁盘控制器找到该扇区头标时,根据其任务是写扇区还是读扇区,来决定是转换写电路, 还是读出数据和尾部记录。找到扇区后,磁盘控制器必须在继续寻找下一个扇区之前对该扇区的信息进行后处理。如果是读数据,控制器计算此数据的ECC码,然 后,把ECC码与已记录的ECC码相比较。如果是写数据,控制器计算出此数据的ECC码,与数据一起存储。在控制器对此扇区中的数据进行必要处理期间,磁 盘继续旋转。

索引的概念

索引是帮助MySQL高效获取数据的排好序数据结构(划重点:排好序) (形象点就是教科书的目录) 索引存储在文件里(也就是说有IO操作2018101412023335

首先,如果数据没有索引,那么我们读取数据是这样的 20181014132220563

二叉树

上面我们发现读取数据特别耗时,那有没有比较节时的数据结构,我们可以看看二叉树

20181014134451765 上面虽然优化了,但是mysql为什么选择 B+Tree

这里介绍一个动态演示数据结构的网址 效果比较直白 相对好理解:www.cs.usfca.edu/~galles/vis…

二叉树与红黑树的比较

20181014141549866 从上面我们发现,红黑树相比较于二叉树又进步了一些,但红黑树还是有些问题:那就是数据量大的话,红黑树的深度会很深,也就是说深度不可控,这样一来查找数据还是会很耗时 2018101414312537 我们发现,相比较于红黑树,hash可以固定“深度”,且映射到磁盘存储引用,这样查找数据直接告诉磁盘数据在哪,查找数据也挺快的,但是 hash 还是有些不足:那就是不能范围查找,比如我们查找Col1>1的数据,当然如果我们查询操作很少的话,我们也可以选择hash数据结构,因为它查找数据挺快的,这也是mysql的索引方法除了B+Tree还有hash

BTree

20181014145506497 我们发现BTree又进步了一些,查询速度提高,存储容量也没影响到。当然有人可能会这样想,那我们为什么不把数据全部都存在一个节点,这样深度不就是1了吗?

当然不行了!java拿取数据一般是这样的:java程序-->CPU--->内存---->硬盘,而内存与硬盘的交互是有大小限制的,是一页数据4k左右,所以不能把所有数据都放在一个节点来获取,一般来说节点会尽量预存4K容量。

看到这里,我们知道(4K=节点;节点=小节点*小节点的容量)一个节点是4K,而节点内有几个小节点,那么也就是说,只要我们每个的小节点的data容量越小,那么可以存的节点也就可以更多。

B+Tree

20181014145506497

B+Tree通过把data不放在非叶子节点来增加度(小节点),一般会一百个以上使得深度是3~5,从而减少查询次数。并且,叶子节点之间会有指针,数据又是递增的,这使得我们范围查找可以通过指针连接查找,而不再从上面节点往下一个个找。 结论:B+Tree 既减少查询次数又提供了很好的范围查询

MyISAM索引实现(非聚集)

MyISAM索引文件和数据文件是分离的,文章一开始也介绍了,数据.MYD+结构.frm+索引.MYI三个文件 那MyISAM的索引是什么样的? a

InnoDB索引实现(聚集)

数据文件本身就是索引文件 表数据文件本身就是按B+Tree组织的一个索引结构文件 聚集索引-叶节点包含了完整的数据记录 为什么InnoDB表必须有主键,并且推荐使用整型的自增主键? 为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间) b

联合索引的底层存储结构

c

MySQL为什么需要一个主键?

u=3496img

主键意味着表中每一行都应该有可以唯一标识自己的一列(或一组列)。 一个顾客可以使用顾客编号列,而订单可以使用订单ID,雇员可以使用雇员ID 或 雇员社会保险号。

主键(primary key) 一列(或一组列),其值能够唯一区分表中的每个行。 唯一标识表中每行的这个列(或这组列)称为主键。没有主键,更新或删除表中特定行很困难,因为没有安全的方法保证只设计相关的行。

虽然并不总是都需要主键,但大多数数据库设计人员都应保证他们创建的每个表有一个主键,以便于以后数据操纵和管理。

表中的任何列都可以作为主键,只要它满足以下条件:

1、任何两行都不具有相同的主键值

2、每个行都必须具有一个主键值(主键列不允许NULL值)

主键值规范:这里列出的规则是MySQL本身强制实施的。

关于主键的几个好习惯 除MySQL强制实施的规则外,应该坚持的几个普遍认为的最好习惯为:

1、 不更新主键列的值

2、不重用主键列的值

3、不在主键列中使用可能会更改的值(例如,如果使用一个名字作为主键以标识某个供应商,应该供应商合并和更改其名字时,必须更改这个主键)

总之:不应该使用一个具有意义的column(id 本身并不保存表 有意义信息) 作为主键,并且一个表必须要有一个主键,为方便扩展、松耦合,高可用的系统做铺垫。

主键的作用,在于索引 无特殊需求下Innodb建议使用与业务无关的自增ID作为主键。

InnoDB引擎使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)

1、如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

2、如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置:

此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

在使用InnoDB存储引擎时,如果没有特别的需要,请永远使用一个与业务无关的自增字段作为主键。

InnoDB 存储引擎采用了聚集(clustered)的方式,因此每张表的存储都是按主键的顺序进行存放。如果没有显式地在表定义时指定主键,InnoDB存储引擎会为每一行生成一个6字节的ROWID,并一次作为主键。

mysql 在频繁的更新、删除操作,会产生碎片。而含碎片比较大的表,查询效率会降低。此时需对表进行优化,这样才会使查询变得更有效率

关注公众号:java宝典 pic222

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/70791
 
195 次点击