B+树代写代做、代做B+树 java 程序

日期：2018-07-25 07:30

用B+树（或者其他数据结构如B树）实现一个简易数据库，每一组数据包含一个键(key)和其值(value)，（这里<key-value>对可以默认为<string,string>对）

你实现的存储系统需要将每组数据的内容保存在磁盘中，并且能够根据名字查找对应的内容，进行查找（支持单键查找和范围查找）、删除、修改操作。范围查找指的是查找在[key1， key2]之间的数据（闭区间）。

需要采用C++类及面向对象设计。不能采用传统的C的结构化设计风格来组织代码。

以下给出了一个例子，你可以不按照例子来设计接口：

class database {

public:

// For query

string get(constint key);

string[]getRange(constint key1, constint key2);

// For insertion and modification

string put(constint key, const string& value);

// for remove

string remove(constint key);

};

附加描述（参考，可以不看）：

你可以将全部索引保存在一个文件中，或者保存在多个文件中，甚至采用二级索引以便减小单个索引文件的大小。数据文件你也可以将其全部保存在一个文件中，或者保存在多个文件中。但不允许以每组数据（名字和其内容）为单位单独保存在一个文件中，索引和数据文件需要分开。

相比于内存读写，磁盘读写的速度是很慢的。所以系统应该尽可能多的访问内存。这时系统把内存当作一个缓存。例如当索引文件被读取到内存后，接下来对索引文件的访问就变成了内存访问。对于数据文件也有相同的道理，当读取一条数据时，系统把它放在内存中，接下来的读写操作都变成了内存操作。当然系统不可能把所有的数据都读到内存中来（那样就变成了内存型数据库），当内存中缓存的数据变过多时，系统应该把一些数据写回到磁盘以释放内存空间。

缓存的问题在于系统运行时不能够将所有的数据存放在内存中，因此一份数据可能同时出现在磁盘和内存中。你需要考虑何时对文件进行读写以便保持文件的一致性，且保证运行效率。

常见的方法有两种，一种是在每次（写）操作后立刻把数据写入磁盘，另一种是新增一个flush接口。只有当用户显式调用flush操作，flush之前的写操作才会被写入磁盘。前者提供较强的一致性，但性能较差，而后者的一致性保证较弱，但性能较好。当然，当缓存空间不足时，也需要把一些数据写回到磁盘。