MySQL数据库设计总结

什么是B-Tree

PHPer 2018-09-16 1482 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
    您需要登录后才可以评论。 立即注册
    相关内容

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

    什么是 SSL、TLS 和 HTTPS?

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

    在最近的会议上。在结束过程中,马斯克(Elon Musk)所说的“为意识之光而...

    what does Elon meant by "Fight for the light of consciousness" ?

    从24对染色体到23对染色体,人类的祖先到底经历了什么?

    有23对染色体的动物除了人还有其他吗?

    推荐内容

    分享几个好用的bt搜索bt资源下载网址网站

    影视电影剧集动漫综艺bt资源在线播放网址网站推荐分享

    全网最新bt磁力搜索引擎bt资源bt网站网址分享

    怎样使用V2Ray代理和SSTap玩如魔兽世界/绝地求生/LOL台服/战地3/黑色沙漠/彩...

    sstap游戏代理教程 从此玩如魔兽世界/绝地求生/LOL台服/战地3/黑色沙漠/彩虹六...

    使用V2Ray的mKCP协议加速游戏

    v2rayN已停止工作