Tree的实现

实现高并发的Btree结构从内存到磁盘的映射(草稿，未完成）

一、问题介绍

对于一个数据库管理系统来说, BTree是它实现存储管理的基础.

 

实现一个原理简洁,并发性能好的BTree,是实现数据较高性能的基本要求.

所以我们用最新的,又成熟BTree结构.

 

而实际的论文通常是内寸结构形式来描述的。理解它，并较高效实现从

内存到磁盘的映射对没有经验的人来说是个不小的挑战.

 

二、普通对象和有内存对象的区别

1.Java提供的工具

  java提供对象序列化工具，它实现java对象的序列化大磁盘，然后可以从磁盘中反序列化出来。

  要实现只要有以下一种接口

• Serializable

      该接口是一个无方法的接口， 当一个Class实现该接口时，它的对象可以直接被writeObjet()，

      而readObject()来实现反序列化(有意思的是：反序列化过程中，它不会调用Class的构造方法）.

     它有几个缺点，就是我们不能控制那个Field不用序列化（这个可以用transient部分解决），

　　 不清楚它对象的各个Field存在什么位置， 本身对象占多少字节。

     所以它一般用于,不在乎对象大小的情况，比如状态对象，和对象的网络传输

• Extenalizable

    该接口要实现两方法　writeExternal(ObjectOutput out）和readExternal(ObjectInput in）（它会调用调用Class的缺省构造方法)

2.直接对byte array存储操作

　　　这是最原始，也是直接的控制Btree对象的序列化，和反序列化。

　　　它是直接要把存储的对象，转换成byte　array, 然后把它写入磁盘，反序列花时也是先读出byte array, 然后把她转化成对象

 

三、我的BTree的实现

　　由于初次写BTree的映射实现，　我首先采用直接byte array 操作，　然后进行refactor,希望有好的结构，然后想利用java Externalizable 接口

    Btree的磁盘映射，当然是以Block（１０２４　＊　２^n bytes)  为单位，每个Block存储Btree的一个node

  

 1. 直接对byte array存储操作的实现

     实现大致分为一下几步

•  
  • 定义Btree Header 在block存储的结构
  • 定义每个Node在Block上的存储
  • 建立Btree class

     先讲讲Btree class的结构

     同内寸对象不同的， 除了class 的构造涵数，应该包括以下方法

1.  
   1.  createBtree() 创建一个新的Btree
   2.  opneBtree() 从磁盘中读去Btree
   3. writeBtree() 把Btree写回磁盘