Hash index 实验中的Split Imgage Index

在extendible hash index中，当插入导致bucket分裂或者移除导致bucket合并时，我们都要找到待分离或合并的bucket的另一半。

分裂bucket时找另一半

分裂bucket分两种情况，

全局深度等于bucket的局部深度

这种情况下需要将将全局深度加一，并将新添入的directory entry指向正确的bucket，举个例子：
现在的全局深度为1，两个bucket的局部深度也为1，kv将要插入第一个桶，但是这个桶已经是满的，为此必须将directory entry翻倍

对于给定bucket的directory index x，另一半bucket的directory index = x ^ (1 << global depth) = x ^ (1 << local depth)，其中global depth是插入前的全局深度，且等于bucket的局部深度。

全局深度大于bucket的局部深度

这种情况只需要增加局部深度，分配新桶，将原本指向同一个bucket的两个directory中的一个指向新桶，举个例子：
现在的全局深度为2，00和10指向的桶局部深度为1，待插入的key的hash值为00，为10分配一个新桶

对于给定bucket的directory index x，另一半bucket的directory index = x ^ (1 << local depth)，其中local depth是插入前bucket的局部深度。

合并时找另一半

lab的网页上写了合并的时机：bucket为空并且另一半和它的深度相同时。要删除的kv的directory要指向另一半的bucket，并且要判断此时是否可以将全局深度减1。举个例子：
现在的全局深度为2，kv从绿色指向的桶中删除后，需要将绿色的directory指向红色的bucket。

对于给定bucket的directory index x，另一半bucket的directory index = x ^ ((1 << (local depth - 1))，其中local depth为插入前bucket的局部深度，并且大于0。

小结

从上面式子可以看出，分离和合并时找另一半的方法是不同的，实现时GetSplitImageIndex要处理这不同的情形。