高性能设计与数据库各种树结构

  1. B+树:传统关系型数据库广泛采用B+树,B+树是对数据排好序后再存储,加快数据检索速度。

    目前大多数DB多采用两级索引的B+树,树的层次最多三层。因此可能需要5次磁盘访问才能更新一条记录(三次磁盘访问获得数据索引及行ID,一次数据文件读操作,一次数据文件写操作,终于知道数据库操作有多麻烦多耗时了)
  2. LSM树:NoSQL(例如:HBase)产品广泛采用LSM树。

    具体思想是:将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘。不过读取的时候稍微麻烦,需要合并磁盘中历史数据和内存中最近的修改操作,所以写入性能大大提升,读取时可能需要先看是否命中内存,否则需要访问较多的磁盘文件。

    LSM树的原理是:把一棵大树拆分成N棵小树,它首先写入内存中,随着小树越来越大,内存中的小树会被清除并写入到磁盘中,磁盘中的树定期可以做合并操作,合并成一棵大树,以优化读性能。

常用操作系统响应时间表

B+树

B*树

LSM树

参考:

平衡二叉树、B树、B+树、B*树

【面试现场】为什么MySQL数据库要用B+树存储索引?

性能测试与高性能架构

大型网站技术架构:核心原理与案例分析


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 using1174@foxmail.com

文章标题: 高性能设计与数据库各种树结构

文章字数: 396

本文作者: Jun

发布时间: 2019-03-26, 14:57:00

最后更新: 2019-03-26, 15:16:12

原始链接: http://yoursite.com/2019/03/26/高性能设计与数据库各种树结构/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏