Author: Sixing Yan
在SimpleDB-3.00中，相对于原有的静态哈希索引技术，我们将实现一种动态哈希索引技术，线性哈希索引技术。相关算法的可以参考这篇文章。
该哈希索引的核心思想是，当一个哈希桶被填满时，将该哈希桶分裂成 新&旧哈希桶，其中将有一般左右的数据从旧哈希桶移动到新哈希桶。查询时，通过对比哈希键（key）的值与分裂点游标，判断当前桶是否已经被分裂，如果被分裂，则用“升级的”哈希函数重新计算键值，找到目标数据所在的哈希桶。
在具体实现中，相比于静态索引仅需一个（种）索引文件，线性哈希索引需要两个（种）索引文件。两个索引文件分别是：存储线性哈希函数参数的索引文件，存储具体数据映射地址的哈希桶。
linear structure.jpg
根据这篇文章示意的函数算法， 我们可以在SimpleDB-3.00中实现线性哈希索引技术，该类的工作流程如下。
linear hash.jpg
首先，初始实例化一个LinearHashIndex类，除了（保留地）为当前索引名（idxname），涉及的表的Schema信息（sch）以及当前的事务（tx），还需要初始化线性哈希方程initLinearHash。
初始化线性哈希方程时，
- 检查方程文件是否存在（
tx.size("lnrhshcat") == 0），如果不存在则新建。
使用tableMgr来新建一个table结构的文件，每一条记录即是一个索引的哈希函数的参数 - 接着检查该索引的哈希方程是否存在（
flag != true），如果不存在则新建（createFunction()）。
通过遍历方程文件来查找是否有符合条件的函数，如果没有 则向方程文件插入一条记录。同时新建默认个数的哈希桶文件，该桶文件使用table结构。
public class LinearHashIndex {
public static int DFLT_COUNT = 25;
public static int DFLT_SIZE = 100;
public static int DFLT_ROUND = 1;
public static int DFLT_SPLIT = 0;
private String idxname;
private Schema sch;
private Transaction tx;
private Constant searchkey = null;
private TableScan ts = null;
private int round; // 第几回合
private int split; // 分裂点坐标
private int size; // function的最大bucket数量
private int count; // 目前有多少个bucket
private RID funcRid;
private TableInfo funcTi;
/**
* Opens a hash index for the specified index.
* @param idxname the name of the index
* @param sch the schema of the index records
* @param tx the calling transaction
*/
public LinearHashIndex(String idxname, Schema sch, Transaction tx) {
this.idxname = idxname;
this.sch = sch;
this.tx = tx;
initLinearHash();}
public void initLinearHash() {
String functbl = this.idxname + "func";
Schema funcsch = new Schema();
funcsch.addStringField("funcname", MAX_NAME);
funcsch.addIntField("round");
funcsch.addIntField("size");
funcsch.addIntField("count");
funcsch.addIntField("split");
if (tx.size("lnrhshcat") == 0) // if the function file no exists
// create linear-hash file
SimpleDB.mdmgr().tblmgr.createTable("lnrhshcat", funcsch, this.tx);// tablemgr
// open linear-hash file
this.funcTi = new TableInfo(functbl, funcsch);
// get the related record
RecordFile fcatfile = new RecordFile(this.funcTi, tx);
Boolean flag = false;
while (fcatfile.next())
if (fcatfile.getString("funcname").equals(tblname)) {
flag = true;
this.size = fcatfile.getInt("size");
this.count = fcatfile.getInt("count");
this.split = fcatfile.getInt("split");
this.round = fcatfile.getInt("round");
break;
}
if (flag != true) // if there no exist the related record
createFunction(funcTi);}
public void createFunction(TableInfo funcTi) {
// a record of parameter into tblcat
RecordFile fcatfile = new RecordFile(funcTi, tx);
fcatfile.insert();
fcatfile.setInt("funcname", funcTi.fileName());
fcatfile.setInt("round", DFLT_ROUND);
fcatfile.setInt("size", DFLT_SIZE);
fcatfile.setInt("count", DFLT_COUNT);
fcatfile.setInt("split", DFLT_SPLIT);
fcatfile.close();
// record the information of current function
this.funcRid = fcatfile.currentRid();
this.count = DFLT_COUNT;
this.size = DFLT_SIZE;
this.round = DFLT_ROUND;
this.split = DFLT_SPLIT;
//initial default buckets
for (int bkt = 0; bkt < this.count; i++)
SimpleDB.mdmgr().tblmgr.createTable(this.idxname + bkt, this.sch, this.tx) // tablemgr}
...
}
public class LinearHashIndex {
public static int DFLT_COUNT = 25;
public static int DFLT_SIZE = 100;
public static int DFLT_ROUND = 1;
public static int DFLT_SPLIT = 0;
private String idxname;
private Schema sch;
private Transaction tx;
private Constant searchkey = null;
private TableScan ts = null;
private int round; // 第几回合
private int split; // 分裂点坐标
private int size; // function的最大bucket数量
private int count; // 目前有多少个bucket
private RID funcRid;
private TableInfo funcTi;
...
public void beforeFirst(Constant searchkey) {
close(); // end up the scan on the last file
this.searchkey = searchkey;
int bucket = linearHash();
String tblname = idxname + bucket;
TableInfo ti = new TableInfo(tblname, sch); // this will open a bucket
this.ts = new TableScan(ti, tx);
}
private int linearHash() {
int key = this.searchkey.hashCode();
int bktnum = hash(key, this.round);
if (bktnum < this.split)
bktnum = hash(key, this.round + 1);
return bktnum;}
private int hash(int key, int round) {return key % (this.count * round);}
...
}
