MySQL数据库设计总结

什么是B-Tree

PHPer 2018-09-16 145次浏览 0条评论 0 0 0
B-Tree就是我们常说的B树,一定不要读成B减树,否则就很丢人了。B树这种数据结构常常用于实现数据库索引,因为它的查找效率比较高。磁盘IO与预读磁盘读取依靠的是机...

B-Tree就是我们常说的B树,一定不要读成B减树,否则就很丢人了。B树这种数据结构常常用于实现数据库索引,因为它的查找效率比较高。

磁盘IO与预读

磁盘读取依靠的是机械运动,分为寻道时间、旋转延迟、传输时间三个部分,这三个部分耗时相加就是一次磁盘IO的时间,大概9ms左右。这个成本是访问内存的十万倍左右;正是由于磁盘IO是非常昂贵的操作,所以计算机操作系统对此做了优化:预读;每一次IO时,不仅仅把当前磁盘地址的数据加载到内存,同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明:当访问一个地址数据的时候,与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页(page)(注:此说法不准确)。一页的大小与操作系统有关,一般为4k或者8k。这也就意味着读取一页内数据的时候,实际上发生了一次磁盘IO。

(注:这里一次磁盘IO的说法不准确,我在网上找到一个比较准确的说法:

单个IO操作

  当控制磁盘的控制器接到操作系统的读IO操作指令的时候,控制器就会给磁盘发出一个读数据的指令,并同时将要读取的数据块的地址传递给磁盘,然后磁盘会将读取到的数据传给控制器,并由控制器返回给操作系统,完成一个写IO的操作;同样的,一个写IO的操作也类似,控制器接到写的IO操作的指令和要写入的数据,并将其传递给磁盘,磁盘在数据写入完成之后将操作结果传递回控制器,再由控制器返回给操作系统,完成一个写IO的操作。单个IO操作指的就是完成一个写IO或者是读IO的操作。

B-Tree与二叉查找树的对比

  我们知道二叉查找树查询的时间复杂度是O(logN),查找速度最快和比较次数最少,既然性能已经如此优秀,但为什么实现索引是使用B-Tree而不是二叉查找树,关键因素是磁盘IO的次数。

数据库索引是存储在磁盘上,当表中的数据量比较大时,索引的大小也跟着增长,达到几个G甚至更多。当我们利用索引进行查询的时候,不可能把索引全部加载到内存中,只能逐一加载每个磁盘页,这里的磁盘页就对应索引树的节点。

一、 二叉树

我们先来看二叉树查找时磁盘IO的次:定义一个树高为4的二叉树,查找值为10:

cf51c71c20_normal.png

第一次磁盘IO:

2d492f04f3_normal.png

第二次磁盘IO

b420f59795_normal.png

第三次磁盘IO:...

登录 | 立即注册

更新于:2018-09-16 15:33:14
    您需要登录后才可以评论。 登录 | 立即注册
    相关内容

    什么是 SSL、TLS 和 HTTPS?

    原文链接:https://www.websecurity.digicert.com/zh/cn/security-topics/what-is-ssl-tls-https 什么是 S...

    CN2和IPLC专线服务器有什么区别,哪个更好?

    原文链接:https://pc6a.com/2093.html2019-12-17 09:52:46昨天有个小朋友搜索CN2和IPLC专线服务器哪个好,小白组织下就是想问:CN2和IPLC专线服务器有什么区别,...

    网站如何知道浏览器的用户在使用什么语言

    http://www.360doc.com/content/15/1110/21/3884271_512215449.shtml我们会看到很多支持多语言的网站,有些早期的网站在首页会有一个链接,让用户自己来选希望...

    Mysql问题整理

    这里整理下Mysql使用中遇到的各种问题

    Yii2数据库报错-SQLSTATE[HY093]: Invalid parameter number: no parameters were bound

    Mysql server has gone away 报错原因分析及解决办法

    mysql 警告 could not be resolved: Name or service not known

    Mysql用特殊字符设置密码遇到的问题

    Mysql的函数substring使用注意事项

    MySQL 5.7内存使用分析

    mysql 命令整理

    【mysql】主键、普通索引、唯一索引和全文索引的比较

    没有接收到要导入的数据。可能是文件名没有提交,也可能是文件大小超出 PHP 限制。

    Mysql知识学习

    MySQL 8.0 索引特性1-函数索引

    MySQL 8.0 索引特性1-函数索引

    MySQL字符串函数substring:字符串截取

    Mysql的临时变量取值3例

    mysql查找字符串出现位置

    推荐内容

    MySQL数据库设计总结

    规则1:一般情况可以选择MyISAM存储引擎,如果需要事务支持必须使用InnoDB存储引擎。注意:MyISAM存储引擎 B-tree索引有一个很大的限制:参与一个索引的所有字...

    什么是B-Tree

    二叉查找树、平衡二叉树、红黑树、B-/B+树性能对比

    使用Yii2遇到的问题整理

    Yii的东西很多,学习和使用的时候遇到了各种各样的问题,这里记录整理下,方便大家分享。composer安装kartik-v/yii2-mpdf时报错,这里记录下 Yii2用compos...

    Yii2用composer更新时遇到的错误

    Yii2 用composer update 时提示'git' 不是内部或外部命令,也不是可运行的程序或批处理文件

    Yii2​用composer安装kartik-v/yii2-mpdf时报错,成功解决后,再让其支持中文。

    使用Yii2的setFlash和bootstrap.min.js遇到的问题,bootstrap.min.js的bug?

    Yii2的action不支持大小写吗?其实是支持的

    composer install 使用tips-网上找的composer install的使用技巧方法

    关于编程时遇到意想不到的错误如何解决

    比如当你写的一个php脚本执行出现问题,如果你的脚本里自己带了对错误的处理,可能会显示那里出错了。或者你用的框架,框架里有debug模式,会报错。

    查问我看笔记功能的实现过程-全文搜索待开启,试试yiisoft/yii2-sphinx

    查问我看笔记功能的实现的重点就是全文搜索,如果不用Yii自带的ActiveRecord的话,就要找扩展,先找了个yii-xunsearch,不行太差了,又找了yiisoft/yii2-elasticsearch,...

    yii2框架中使用sphinx使用搜索引擎 多条件选择搜索

    运行php composer.phar require --prefer-dist yiisoft/yii2-sphinx

    基于CentOS7 Centos8平台搭建邮件服务器

    EwoMail​在Centos8上安装了,各种坑,各种报错。这个集成包太臃肿了。 20200416 EwoMail 已经弃用,国内的一家公司搞的坑爹产品。 20200418

    如何在RHEL8 / CentOS8上安装Webmin

    设置postfix作为邮件发送服务器