B-Trees【设计数据密集型应用】

ShowerSun 发布于2019-05-28 18:41 / 2258人阅读

摘要：日志结构的索引虽然目前得到认可，但是它不是最常见的索引类型，应用最广泛的索引类型是。许多非关系数据库也在用它。这种设计与硬件对应的很密切，因为磁盘也是按照固定的尺寸排列的。之间的表示范围边界。一个四层的，是的可以存储高达的数据

B-Trees

日志结构的索引虽然目前得到认可，但是它不是最常见的索引类型，应用最广泛的索引类型是B-Tree。

在几乎所有数据库中B-Tree仍然是索引的标准实现。许多非关系数据库也在用它。

像SSTable一样，B-Tree把键值对按照key排序，这样就保证了键值对的高效查询和范围查询（range query）。但是这也是相似之处的结束点：B-Tree的设计哲学非常之不同。

日志结构的索引把数据库划分成可变尺寸的segment，一般几M或更多。按照顺序写每一个segment。与之相反的是，B-Tree把划分成固定尺寸的block或page，一般4K或更多，一次读或写一个page。这种设计与硬件对应的很密切，因为磁盘也是按照固定的尺寸排列的。

可以通过地址或者位置可以找到一个具体的page，同时一个page也可以引用另外一个page，和指针类似，但是是在磁盘上而不是在内存中。我们可以用这些page的引用来构建一棵树。如图3-6

B-Tree中一个page被设计为root，查询的时候从root开始。每个page包含几个key和子page的reference，每个子page负责一个连续key的范围。reference之间的key表示范围边界。

B-Tree中一个page中的子page的reference的数量叫做branching factor。实战中，branching factor取决于存储reference和range边界的所需要的空间，通常是几百。

如果你想要更新key对应的值，搜索到叶子page后，直接修改，然后写回磁盘就可以了。如果想要添加key，找到范围包含那个key的page，添加就行了。如果page空间不足，就把那个page分成两半，父亲page被更新，并且负责新的key范围的分支。

这个算法确保了树一直保持平衡：一个n个key的B-Tree，其深度是O（logn）。大部分数据库可以容纳3或4层的B-tree。所以查询的时候不用遍历很多的reference。（一个四层4KB的page，branching factor是500的B-tree可以存储高达256TB的数据）

混合云服务器托管 io密集型云主机 io密集型云vps 应用网站设计 mongodb应用设计模式

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/8331.html

第5节复制(replication)【设计数据密集型应用】

摘要：节点必须锁住所有写操作，直到同步复制响应或恢复正常。节点能很快恢复，因为记录了故障发生前的最后一次。这样会违反客户对数据持久化的期望。多久合适在宣布死亡之前时间长，节点故障恢复时间就长。当有并发同时执行时，这会成为限制。 Replication（复制） Replication就是把相同的数据复制到多个机器上。有如下几个原因让数据的地理位置离用户更近（以减少延迟）保证系统仍然能提供...

Lyux 2019-05-28 18:41 评论0 收藏0
百度X-MAN超级AI计算平台，人工智能界的超级英雄

摘要：当地时间月日，在加拿大举行的第届神经信息处理系统大会上，百度正式发布自主研发的超级计算平台。自年诞生以来，百度超级计算平台历经代发展，次架构升级，创造项业界第一，同时期关键技术性能保持领先，引领行业发展趋势。当地时间12月2日，在加拿大举行的第32届NeurIPS神经信息处理系统大会上，百度正式发布自主研发的超级AI计算平台X-MAN3.0。该平台专为AI深度学习场景优化设计，每秒完...

CoyPan 2019-07-24 16:03 评论0 收藏0
百度X-MAN超级AI计算平台，人工智能界的超级英雄

摘要：当地时间月日，在加拿大举行的第届神经信息处理系统大会上，百度正式发布自主研发的超级计算平台。自年诞生以来，百度超级计算平台历经代发展，次架构升级，创造项业界第一，同时期关键技术性能保持领先，引领行业发展趋势。当地时间12月2日，在加拿大举行的第32届NeurIPS神经信息处理系统大会上，百度正式发布自主研发的超级AI计算平台X-MAN3.0。该平台专为AI深度学习场景优化设计，每秒完...

wenzi 2019-07-16 16:37 评论0 收藏0
AIOps在携程的践行

摘要：随着人工智能时代的到来，携程生产环境运维进入了新的运维时代。本文选取了几种典型的运维场景对在携程的践行展开了介绍，首先让我们从概念认识下。针对应用异常指标检测这种场景，抽取一定的样本统计，在基于专家经验标注下的准确率可达到以上，召回率接近。作者简介徐新龙，携程技术保障中心应用管理团队高级工程师，负责多个AIOps项目的设计与研发。信号处理专业硕士毕业，对人工智能、机器学习、神经网络及数学有...

MingjunYang 2019-04-25 17:22 评论0 收藏0
IBM发布新的AI解决方案，将深度学习训练时间从数周缩短到数小时

摘要：这种分布式版本的利用了加速服务器的虚拟化集群，这些集群采用经济高性能的计算方法，将深度学习的训练时间从数周缩短到数小时。 IBM今日宣布推出了一款新的 PowerAI 深度学习软件，该软件基于 Power Systems 而构建，可帮助数据科学家与开发人员解决所面临的挑战，具体来说：它可以提供丰富的工具和数据准备功能，简化开发体验，还可以将 AI 系统训练所需的时间从数周缩短到数小时。数据科...

GraphQuery 2019-04-25 18:14 评论0 收藏0