BosCollege-SimpleDB-线性哈希索引

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);}
      ...
}