【分布式存储】数据存储和检索～B+树-Toy模板网

这篇具有很好参考价值的文章主要介绍了【分布式存储】数据存储和检索～B+树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

为什么数据存储结构重要

在存储系统中，其实不管数据是什么样的，归根结底其实都还是取决于数据的底层存储结构，而主要常见的就是数据库索引结构，B+树、Redis中跳表、以及LSM、搜索引擎中的倒排索引。本质都是如何利用不用的数据结构，在性能和存储空间之间权衡。数据写的速度和读取数据。

MySQL中索引如何用B+树实现的

常用数据结构分析

哈希表： 哈希表以O（1）的查询效率著名，但是其本身是用空间换时间。并且不支持范围查询。
平衡二叉查找树： 查询和写入都是O(logN) 进行中序遍历的话，可以得到一个有序的数据序列，但是不支持快速查找。
跳表： 跳表，其实是通过多层的链表结构实现，可以快速查询、删除、插入都是O(LogN)
【分布式存储】数据存储和检索～B+树,# 数据库原理,# 数据结构与算法,# 分布式存储,分布式,b树,数据结构
而B+树和跳表十分相视。

B+树

【分布式存储】数据存储和检索～B+树,# 数据库原理,# 数据结构与算法,# 分布式存储,分布式,b树,数据结构
我们从从一个二叉查找树进行改造，将非叶子节点不存储数据，由叶子节点存储数据。并且叶子节点通过指针可以前后引用。这样，当我们查找数据的时候，找到15。然后可以通过遍历.next 就可以进行范围查询。这就是为什么叶子节点需要双向链表进行引用。

如果将全部的数据都存储到内存中，那么内存是放不下的，所以一个方式就是，只将根节点存储在内存中，其他节点存储在磁盘上。
而二叉查找数因为数据如果较多，树的高度就会更高，查询的IO次数更多。
【分布式存储】数据存储和检索～B+树,# 数据库原理,# 数据结构与算法,# 分布式存储,分布式,b树,数据结构
所以一般使用固定阶段，3层来保证数据查询的IO次数。操作系统读取数据是按照Page 64KB进行读取。所以我们尽量让每个节点存储的数据等于一页的大小。