0.写在前面
Homework2的一些知识总结。题目和sol可以去cmu-15-445 2020上找到。
个人学习总结:https://github.com/kaniel-outis/CMU15-445
Question 1: Cuckoo Hashing
cuckoo是布谷鸟的意思,这种鸟有一种即狡猾又贪婪的习性,它不肯自己筑巢, 而是把蛋下到别的鸟巢里,而且它的幼鸟又会比别的鸟早出生,布谷幼鸟天生有一种残忍的动作,幼鸟会拼命把未出生的其它鸟蛋挤出窝巢,今后以便独享“养父 母”的食物。cuckoo hashing的思想和布谷鸟类似。
基本思想:使用2个hash函数来处理碰撞,从而每个key都对应到2个位置。
插入操作如下:
-
对key值hash,生成两个hash key值,hash_key_1和 hash_key_2, 如果对应的两个位置上有一个为空,那么直接把key插入即可。
-
否则,任选一个位置,把key值插入,把已经在那个位置的key值踢出来。
-
被踢出来的key值,需要重新插入,直到没有key被踢出为止。
Question 2: B+Tree
2.1 B+树的定义
1)B+树包含2种类型的结点:内部结点(也称索引结点)和叶子结点。根结点本身即可以是内部结点,也可以是叶子结点。根结点的关键字个数最少可以只有1个。
2)B+树与B树最大的不同是内部结点不保存数据,只用于索引,所有数据(或者说记录)都保存在叶子结点中。
3) m阶B+树表示了内部结点最多有m-1个关键字(或者说内部结点最多有m个子树),阶数m同时限制了叶子结点最多存储m-1个记录。
4)内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
5)每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接。
2.2 B+树的插入操作
1)若为空树,创建一个叶子结点,然后将记录插入其中,此时这个叶子结点也是根结点,插入操作结束。
2)针对叶子类型结点:根据key值找到叶子结点,向这个叶子结点插入记录。插入后,若当前结点key的个数小于等于m-1,则插入结束。否则将这个叶子结点分裂成左右两个叶子结点,左叶子结点包含前m/2个记录,右结点包含剩下的记录,将第m/2+1个记录的key进位到父结点中(父结点一定是索引类型结点),进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点,然后执行第3步。
3)针对索引类型结点:若当前结点key的个数小于等于m-1,则插入结束。否则,将这个索引类型结点分裂成两个索引结点,左索引结点包含前(m-1)/2个key,右结点包含m-(m-1)/2个key,将第m/2个key进位到父结点中,进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点,然后重复第3步。
2.3 B+树的删除操作
如果叶子结点中没有相应的key,则删除失败。否则执行下面的步骤
1)删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1,删除操作结束,否则执行第2步。
2)若兄弟结点key有富余(大于Math.ceil(m-1)/2 – 1),向兄弟结点借一个记录,同时用借到的key替换父结(指当前结点和兄弟结点共同的父结点)点中的key,删除结束。否则执行第3步。
3)若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点,并删除父结点中的key(父结点中的这个key两边的孩子指针就变成了一个指针,正好指向这个新的叶子结点),将当前结点指向父结点(必为索引结点),执行第4步(第4步以后的操作和B树就完全一样了,主要是为了更新索引结点)。
4)若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1,则删除操作结束。否则执行第5步
5)若兄弟结点有富余,父结点key下移,兄弟结点key上移,删除结束。否则执行第6步
6)当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点,重复第4步。
注意,通过B+树的删除操作后,索引结点中存在的key,不一定在叶子结点中存在对应的记录。
下面是一颗5阶B树的删除过程,5阶B数的结点最少2个key,最多4个key。
回到题目本身。
a)基础的b+树插入。
b) 2,5,4,13。
c) 注意删除时候兄弟节点富余之后的操作。
Question 3: Extendible Hashing
这要是课上提到过的hash,主要是二进制的思想。
题目也是比较简单。注意规则即可。
Question 4: Suffix Trees
这部分题目比较简单。
参考内容
B+树操作
Extendible Hashing