MPT树的基本操作

发布时间:2019年03月31日 价值:20000.00 / 共识:24

参考:https://ethfans.org/posts/588

介绍完MPT树的组成结构,在这一章将介绍MPT几种核心的基本操作,也就是我们经常说的 增,删,改,查;为了介绍方便,我们的顺序有变.

一.查(Get)

我们先贴下代码:

  1. func (t *Trie) TryGet(key []byte) ([]byte, error) {
  2. key = keybytesToHex(key) //对原生编码进行Hex编码,这个key其实就是搜索路径
  3. value, newroot, didResolve, err := t.tryGet(t.root, key, 0)//从根节点搜寻与路径内容一致的路径
  4. if err == nil && didResolve {
  5. t.root = newroot
  6. }
  7. return value, err
  8. }
  9. func (t *Trie) tryGet(origNode node, key []byte, pos int) (value []byte, newnode node, didResolve bool, err error) {
  10. switch n := (origNode).(type) {
  11. case nil://如果是个空节点,直接返回空
  12. return nil, nil, false, nil
  13. case valueNode://如果是叶子节点,表示已经找到该节点,直接返回该节点
  14. return n, n, false, nil
  15. case *shortNode://扩展节点
  16. if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) {
  17. // key not found in trie key不是搜索路径的前缀,表示该节点在树中不存在。
  18. return nil, n, false, nil
  19. }
  20. //n.Value为下一个节点的引用,key为前缀,将剩余的搜索路径作为参数,对其子节点递归地调用查找函数
  21. value, newnode, didResolve, err = t.tryGet(n.Val, key, pos+len(n.Key))
  22. if err == nil && didResolve {
  23. n = n.copy()
  24. n.Val = newnode
  25. n.flags.gen = t.cachegen
  26. }
  27. return value, n, didResolve, err
  28. case *fullNode://分支节点
  29. //从Children中找到指向的下一个节点,key为前缀,将剩余的搜索路径作为参数递归地调用查找函数。
  30. value, newnode, didResolve, err = t.tryGet(n.Children[key[pos]], key, pos+1)
  31. if err == nil && didResolve {
  32. n = n.copy()
  33. n.flags.gen = t.cachegen
  34. n.Children[key[pos]] = newnode
  35. }
  36. return value, n, didResolve, err
  37. case hashNode://如果是哈希节点,直接调用t.resolveHash 解析出节点类型,并递归调用查找函数
  38. child, err := t.resolveHash(n, key[:pos])
  39. if err != nil {
  40. return nil, n, true, err
  41. }
  42. value, newnode, _, err := t.tryGet(child, key, pos)
  43. return value, newnode, true, err
  44. default:
  45. panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
  46. }
  47. }

源码部分我加了注释, 为了更形象的表示这个过程。我们通过一幅图进行演示:
查找dog的过程

上图是查找key为”cat”, 节点值为”dog”的过程.

1. keybytesToHex([]byte(“cat”)),将key”cat”转换成hex编码[3,15,3,13,4,10,T] (在末尾添加终止符是因为需要查找一个真实的数据项内容);
2.t.root的节点类型是shortNode(扩展节点),t.root.Key为3,15,t.root.Val是下一个节点的引用。按代码递归地对其子节点进行查找调用,剩余的搜索路径为[3,13,4,10,T];
3.递归过来的node类型为fullNode(分支节点),以搜索路径[3,13,4,10,T]的第一个字节内容3选择第4个孩子节点递归进行查找,剩余的搜索路径为[13,4,10,T];
4.递归过来的node类型为valueNode(叶子节点),,且key与剩余的搜索路径一致,表示找到了该节点,按代码直接将该节点返回。Val为”dog”。

二.增,改(Insert)

插入操作是基于查找过程完成的,我们也先看代码,再分析过程:

  1. // If a node was not found in the database, a MissingNodeError is returned.
  2. func (t *Trie) TryUpdate(key, value []byte) error {
  3. k := keybytesToHex(key)//对原生编码进行Hex编码,这个key其实就是搜索路径
  4. if len(value) != 0 {
  5. _, n, err := t.insert(t.root, nil, k, valueNode(value))//从树根开始查找插入valueNode
  6. if err != nil {
  7. return err
  8. }
  9. t.root = n
  10. } else {
  11. //`````````略
  12. }
  13. return nil
  14. }
  15. func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
  16. if len(key) == 0 {
  17. //如果key为0,则表示value为一个valueNode,则直接将n转为valueNode并和value进行比较。看看是否是合法的valueNode.
  18. if v, ok := n.(valueNode); ok {
  19. return !bytes.Equal(v, value.(valueNode)), value, nil
  20. }
  21. return true, value, nil
  22. }
  23. switch n := n.(type) {
  24. case *shortNode://扩展节点
  25. matchlen := prefixLen(key, n.Key)//首先找到与当前节点拥有最长相同路径前缀的字节数
  26. if matchlen == len(n.Key) {
  27. //如果和该节点的key完全匹配。表示以前有该并节点。只要更新Val值就行了,dirty表示新的value是否和旧的一样,一样为false.
  28. dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
  29. if !dirty || err != nil {
  30. return false, n, err
  31. }
  32. //插入成功后,更新shortNode的值然后返回
  33. return true, &shortNode{n.Key, nn, t.newFlag()}, nil
  34. }
  35. //其他情况说明有不同分支,所以构造一个fullNode,然后再fullNode节点的Children位置调用t.insert插入剩下的两个short节点
  36. branch := &fullNode{flags: t.newFlag()}
  37. var err error
  38. _, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
  39. if err != nil {
  40. return false, nil, err
  41. }
  42. _, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
  43. if err != nil {
  44. return false, nil, err
  45. }
  46. // 如果没有公共前缀部分,则直接返回这个brach节点.
  47. if matchlen == 0 {
  48. return true, branch, nil
  49. }
  50. // 如果有公共前缀,新建公前缀节点,并指向已经插入两个子节点的fullNode,然后return。
  51. return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil
  52. case *fullNode://分支节点
  53. //直接往对应的孩子节点调用insert方法,然后把新生成的节点更新到fullNode对象的孩子节点
  54. dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
  55. if !dirty || err != nil {
  56. return false, n, err
  57. }
  58. n = n.copy()
  59. n.flags = t.newFlag()
  60. n.Children[key[0]] = nn
  61. return true, n, nil
  62. case nil://当前是个空树,直接构造一个shortNode.
  63. return true, &shortNode{key, value, t.newFlag()}, nil
  64. case hashNode:
  65. //hashNode的意思是当前节点还没有加载到内存里面来,还是存放在数据库里面,那么首先调用 t.resolveHash(n, prefix)来加载到内存,然后对加载出来的节点调用insert方法来进行插入
  66. rn, err := t.resolveHash(n, prefix)
  67. if err != nil {
  68. return false, nil, err
  69. }
  70. dirty, nn, err := t.insert(rn, prefix, key, value)
  71. if !dirty || err != nil {
  72. return false, rn, err
  73. }
  74. return true, nn, nil
  75. default:
  76. panic(fmt.Sprintf("%T: invalid node: %v", n, n))
  77. }
  78. }

以上代码我也加了注释进行说明,整个过程从根节点开始,一直往下找,直到找到可以插入的点,进行插入操作。参数node是当前插入的节点, prefix是当前已经处理完的部分key, key是还没有处理玩的部分key, 完整的key = prefix + key。 value是需要插入的值。 返回值bool是操作是否改变了Trie树(dirty),node是插入完成后的子树的根节点, error是错误信息

我们继续用一张图来描述下插入过程:
插入节点

上图是在查找key为”cat”节点的树的基础上插入key为“cau”, value为“dog1”节点的过程。

1.将key”cau”转换成hex编码[3,15,3,13,4,11,T],可以看到和”cat”的hex编码只是最后一位不同。所以“cat”和”cau”的公共前缀是[3,15,3,13,4]这部分。
2.通过查找算法,从树根开始找到左图蓝线圈出的节点node1,且拥有与新插入节点最长的共同前缀[3,15,3,13,4];
3.通过代码可以看到由于(if matchlen == len(n.Key))结果是false,所以就新建了个fullNode,并把”cat”,”cau”不同的前缀部分[10],[11]为key,分别指向之前val是”dog”和”dog1”的节点.也就是图中的”a”指向”dogt”,”b”指向”dog1”
4.插入完成。

三.删(Delete)

删除操作其实和插入操作非常相似,不过我们也将代码分析一遍,和上面一样,我也会在代码中加入注释:

  1. func (t *Trie) TryDelete(key []byte) error {
  2. k := keybytesToHex(key) //同上面一样,对原生编码进行Hex编码,这个key其实就是搜索路径
  3. _, n, err := t.delete(t.root, nil, k)//从树根开始查找,删除路径为k的节点.
  4. if err != nil {
  5. return err
  6. }
  7. t.root = n
  8. return nil
  9. }
  10. // delete returns the new root of the trie with key deleted.
  11. // It reduces the trie to minimal form by simplifying
  12. // nodes on the way up after deleting recursively.
  13. func (t *Trie) delete(n node, prefix, key []byte) (bool, node, error) {
  14. switch n := n.(type) {
  15. case *shortNode://扩展节点
  16. matchlen := prefixLen(key, n.Key)//首先找到与当前节点拥有最长相同路径前缀的字节数
  17. if matchlen < len(n.Key) {
  18. return false, n, nil //没有找到相匹配的路径,返回false.
  19. }
  20. if matchlen == len(key) {
  21. return true, nil, nil //找到相匹配的路径了,将整个node删除,返回true.
  22. }
  23. //如果还有路径,以key当前位置递归查找删除剩余的key路径,
  24. dirty, child, err := t.delete(n.Val, append(prefix, key[:len(n.Key)]...), key[len(n.Key):])
  25. if !dirty || err != nil {//没删除成功
  26. return false, n, err
  27. }
  28. switch child := child.(type) {//如果递归删除了个fullNode的子节点
  29. case *shortNode://如果子节点是个shortNode,则将当前节点的key和子节点的key连在一起,组成一个新的shortNode,并更新Val返回.
  30. return true, &shortNode{concat(n.Key, child.Key...), child.Val, t.newFlag()}, nil
  31. default://如果是其他节点,则不用合并key.直接返回
  32. return true, &shortNode{n.Key, child, t.newFlag()}, nil
  33. }
  34. case *fullNode://分支节点
  35. //删除路径中第一个key标志的节点
  36. dirty, nn, err := t.delete(n.Children[key[0]], append(prefix, key[0]), key[1:])
  37. if !dirty || err != nil {
  38. return false, n, err
  39. }
  40. n = n.copy()
  41. n.flags = t.newFlag()//newFlag()表示 dirty标志置为true,hash标志置空.之前的结果已经不可能用
  42. n.Children[key[0]] = nn
  43. //遍历当前fullNode节点还有几个子节点
  44. pos := -1
  45. for i, cld := range &n.Children {
  46. if cld != nil {
  47. if pos == -1 {
  48. pos = i
  49. } else {
  50. pos = -2
  51. break
  52. }
  53. }
  54. }
  55. //
  56. if pos >= 0 {//大于0表示还有子节点,并且pos不等于 16终止符,表示还有子节点
  57. if pos != 16 {
  58. //如果剩余的子节点是个shortNode,则将key合并,生成一个扩展节点返回
  59. cnode, err := t.resolve(n.Children[pos], prefix)
  60. if err != nil {
  61. return false, nil, err
  62. }
  63. if cnode, ok := cnode.(*shortNode); ok {
  64. k := append([]byte{byte(pos)}, cnode.Key...)
  65. return true, &shortNode{k, cnode.Val, t.newFlag()}, nil
  66. }
  67. }
  68. // 否则,直接以当前的key构造一个扩展节点返回,表示已经是叶子节点.
  69. return true, &shortNode{[]byte{byte(pos)}, n.Children[pos], t.newFlag()}, nil
  70. }
  71. // n still contains at least two values and cannot be reduced.
  72. return true, n, nil
  73. case valueNode://叶子节点,直接返回
  74. return true, nil, nil
  75. case nil:
  76. return false, nil, nil
  77. case hashNode:
  78. //hashNode的意思是当前节点还没有加载到内存里面来,还是存放在数据库里面,那么首先调用 t.resolveHash(n, prefix)来加载到内存,然后对加载出来的节点调用t.delete方法来进行删除,同insert
  79. rn, err := t.resolveHash(n, prefix)
  80. if err != nil {
  81. return false, nil, err
  82. }
  83. dirty, nn, err := t.delete(rn, prefix, key)
  84. if !dirty || err != nil {
  85. return false, rn, err
  86. }
  87. return true, nn, nil
  88. default:
  89. panic(fmt.Sprintf("%T: invalid node: %v (%v)", n, n, key))
  90. }
  91. }

代码看完。我们总结下规则:

1. 找到与需要插入的节点拥有最长相同路径前缀的节点,记为Node;
2. 若Node为叶子/扩展节点(shortNode):”若剩余的搜索路径与node的Key完全一致,则将整个node删除;若node的key是剩余搜索路径的前缀,则对该节点的Val做递归的删除调用,否则删除失败”.
3.若Node为分支节点: 删除孩子列表中相应下标标志的节点;删除结束,若Node的孩子个数只剩下一个,那么将分支节点替换成一个叶子/扩展节点(shortNode);
4.若删除成功,则将被修改节点的dirty标志置为true,hash标志置空(之前的结果已经不可能用),且将节点的诞生标记更新为现在;

删除过程我们也有图,来描述一下:
删除过程

这张图就是删除上面插入的节点(key为“cau”, value为“dog1”)。

1.将key”cau”转换成hex编码[3,15,3,13,4,11,T] ;
2.通过查找算法,找到用叉(X)号表示的节点node1,从根节点到node1的路径与搜索路径完全一致
3.从node1的父节点中删除该节点,父节点仅剩一个孩子节点,故将父节点转换成一个叶子节点;
4.新生成的叶子节点又与其父节点(扩展节点)发生了合并,最终生成了一个叶子节点包含了所有的信息.

最后的树又恢复到了最开始的时候。

OK。关于树的操作。基本上就是这些,不过还有一个非常重要的就是树的存储。我们下篇再介绍.

  • 分享 收藏
0 条评论
  • 这篇文章暂无评论,赶紧评论一下吧~