Author: Sixing Yan
在SimpleDB-3.00中呢燥，相對(duì)于原有的靜態(tài)哈希索引技術(shù)，我們將實(shí)現(xiàn)一種動(dòng)態(tài)哈希索引技術(shù)充易，線性哈希索引技術(shù)菇民。相關(guān)算法的可以參考這篇文章。
該哈希索引的核心思想是持钉，當(dāng)一個(gè)哈希桶被填滿時(shí)衡招，將該哈希桶分裂成 新&舊哈希桶，其中將有一般左右的數(shù)據(jù)從舊哈希桶移動(dòng)到新哈希桶每强。查詢時(shí)始腾，通過(guò)對(duì)比哈希鍵（key）的值與分裂點(diǎn)游標(biāo)，判斷當(dāng)前桶是否已經(jīng)被分裂空执，如果被分裂浪箭，則用“升級(jí)的”哈希函數(shù)重新計(jì)算鍵值，找到目標(biāo)數(shù)據(jù)所在的哈希桶辨绊。
在具體實(shí)現(xiàn)中奶栖，相比于靜態(tài)索引僅需一個(gè)（種）索引文件，線性哈希索引需要兩個(gè)（種）索引文件门坷。兩個(gè)索引文件分別是：存儲(chǔ)線性哈希函數(shù)參數(shù)的索引文件宣鄙，存儲(chǔ)具體數(shù)據(jù)映射地址的哈希桶。
linear structure.jpg
根據(jù)這篇文章示意的函數(shù)算法默蚌， 我們可以在SimpleDB-3.00中實(shí)現(xiàn)線性哈希索引技術(shù)冻晤，該類的工作流程如下。
linear hash.jpg
首先绸吸，初始實(shí)例化一個(gè)LinearHashIndex類鼻弧，除了（保留地）為當(dāng)前索引名（idxname），涉及的表的Schema信息（sch）以及當(dāng)前的事務(wù)（tx）惯裕，還需要初始化線性哈希方程initLinearHash温数。
初始化線性哈希方程時(shí)，
- 檢查方程文件是否存在（
tx.size("lnrhshcat") == 0）蜻势，如果不存在則新建撑刺。
使用tableMgr來(lái)新建一個(gè)table結(jié)構(gòu)的文件，每一條記錄即是一個(gè)索引的哈希函數(shù)的參數(shù) - 接著檢查該索引的哈希方程是否存在（
flag != true）握玛，如果不存在則新建（createFunction()）够傍。
通過(guò)遍歷方程文件來(lái)查找是否有符合條件的函數(shù)甫菠，如果沒(méi)有 則向方程文件插入一條記錄。同時(shí)新建默認(rèn)個(gè)數(shù)的哈希桶文件冕屯，該桶文件使用table結(jié)構(gòu)寂诱。
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; // 分裂點(diǎn)坐標(biāo)
private int size; // function的最大bucket數(shù)量
private int count; // 目前有多少個(gè)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; // 分裂點(diǎn)坐標(biāo)
private int size; // function的最大bucket數(shù)量
private int count; // 目前有多少個(gè)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);}
...
}
