前言

继续做homework,这一部分我们回顾一下lab1中涉及的知识点还有刚刚学的的B+树的内容。(PS:感觉需要回头再看看那本mysql技术内幕了,好书果然需要多看看。。。我都快忘差不多了)

正文

Part1 Extendible Hashing

a)

Bucket size是2,上来只有一个空的bucket,依次插入8,16,4,3,11,12转换为二进制后为

  • 01000
  • 10000
  • 00100
  • 00011
  • 01011
  • 01100

插入8,16后第一个bucket就满了,然后4的后两位都和一样,所以一次分裂肯定不够,global deepth翻到3时就可以了,然后插入18后,先看下后缀是010这个10都没有,所以肯定只需要翻一下就够了,直接是2了(一个一个推导太慢了,反正我是懒得搞)

b)

更简单了同样是将28,30,4,8,34转换为二进制

  • 11100
  • 11110
  • 00100
  • 01000
  • 100010

然后我们看插到8时,会第一次bucket满了,但是注意这时候local depth是小于global depth的所以只会分裂这个bucket,当我们插到34时才会让directory翻倍,然后说删除14和20,那么将directory指针重新分配后,能看到回收了两个bucket,然后看剩下的两个bucket只有最低位是不一样的,所以local depth应该是1

Part2 Linear Hashing

a)

还是转换为二进制26,27,28,29,30

  • 11010
  • 11011
  • 11100
  • 11101
  • 11110

可以看到27先触发满第三个bucket,导致分类

b)

注意linear hash的分裂的桶是分裂点指向的点,所以不是直接分裂满的桶,分裂点的桶的key都要用新的hash来算一遍,填入12,13,19后的应该是这样的

H1H0
000008241632
00101925
0101010
01111311573溢出19
10012
101513

Part3 B+Tree

a)

看下我们要找11到27之间的所有记录,至少需要多少个指针,先找11,小于26,访问一次指针,左边找,然后找第一个小于11的位10,指针+1走10的右边,找到11,取11的指针,现在指针数为3了,然后因为是个有序链表,往右边遍历找到27取27的指针,总共4次指针

b)

  1. 插入10,没有满直接插入就行了,不会画图。。。随便画了个巨丑的图(应该是有多个线对应每个node的,但是我懒得画了😊),每一个node都可以容纳三个数,这里没画出来空格子

  2. 插入10,18,插入10之后如上图,然后要插入18,发现满了需要做分裂,17是中间数需要提上去(根据约定我们取右边的树),然后10,11分裂到左边的node,17,18分裂到右边的节点,类似结果是这个样子

  3. 删除11,删掉11后node小于最低范围了,所以需要从右边借位,然后需要更新下父节点的值,如图

  4. 删除31,删除31后,因为右边没有值可以借了,所以我们需要合并节点,32移到左边的node,然后删除父节点的30,因为父节点没有值了,也触发了一次合并,将最右边的叶子节点的左值提上去,同时删除再上一层的父节点,即这里是根节点26最后得到这样的图。

c)

  1. 插入28,溢出触发分裂,将22往上面提,但是父节点也满了,继续分裂,将22往上提,最后得出的图为

  2. 删除3

    因为右边再删一个就小于范围了,所以不能从右边来取值,触发合并,将8右移放到右边的node,删除父节点中的10,最后的到是

Part4 Skip List and Radix Tree

a)

第一个是跳表,插入20,应该在15和21之间,然后插入的数据是否成为新的索引是抛硬币,所以一路往上可能就是被3或者15指到

b)

不是最优化的,他有可以合并的,直接用答案的图片吧

总结

这次作业还是挺简单的,只要掌握好基本的概念就行了,卑微社畜,继续学习了。