您好,登录后才能下订单哦!
这篇文章主要介绍“go的amt数组算法怎么用”,在日常操作中,相信很多人在go的amt数组算法怎么用问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”go的amt数组算法怎么用”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
type Node struct { Bmap []byte //是否设置值 仅第一个字节游泳。八位代表八个自节点是否存在 Links []cid.Cid //自节点 Values []*cbg.Deferred //Flush 将 expVals设置到Values上面 expLinks []cid.Cid //设置的子节点值 expVals []*cbg.Deferred //设置的值 cache []*Node //子节点缓存 }
amt数据结构是一个八叉树,所有的数据节点都存储在叶子节点上。数组形态就表现在叶子上,把整个树的最底层节点按顺序拼在一起就是amt数组。不存在数据的索引节点会裁减掉,节省所需的数据空间。
通过id确定叶子节点位置
如果该叶子节点所在的索引节点有数据,那么直接设置这个数据即可。
如果叶子节点位于当前树容量之内,但是原来不存在该路径数据,需要新建这个索引路径再把数据挂上去。
如果设置的数据位置超过当前八叉树容量,那么先要扩充当前八叉树深度,原数据作为新树的左子树。新节点新建一条路径挂上写入的叶子节点
//增长层数 for i >= nodesForHeight(width, int(r.Height)+1) { if !r.Node.empty() { if err := r.Node.Flush(ctx, r.store, int(r.Height)); err != nil { return err } c, err := r.store.Put(ctx, &r.Node) if err != nil { return err } r.Node = Node{ Bmap: []byte{0x01}, Links: []cid.Cid{c}, } } r.Height++ } //设置值 addVal, err := r.Node.set(ctx, r.store, int(r.Height), i, &cbg.Deferred{Raw: b}) if err != nil { return err } if addVal { r.Count++ }
添加数据时候,首先通过高度确定最后一层的数量,在通过数组索引需要确定第一层的索引节点,然后递归,通过倒数第二层的数据宽度确定第二层的索引节点,这样层层找到叶子节点数据
func (n *Node) get(ctx context.Context, bs cbor.IpldStore, height int, i uint64, out interface{}) error { subi := i / nodesForHeight(width, height) set, _ := n.getBit(subi) if !set { return &ErrNotFound{i} } if height == 0 { //找到自节点 n.expandValues() d := n.expVals[i] if um, ok := out.(cbg.CBORUnmarshaler); ok { return um.UnmarshalCBOR(bytes.NewReader(d.Raw)) } else { return cbor.DecodeInto(d.Raw, out) } } subn, err := n.loadNode(ctx, bs, subi, false) if err != nil { return err } return subn.get(ctx, bs, height-1, i%nodesForHeight(width, height), out) //递归向下找自节点 }
删除数据先查找到数据位置和路径
如果该数据所在的索引节点上还存在其他数据,直接清除数据,设置标识即可。
删除数据之后层层检查索引节点,如果索引节点下面是空的,那么就删除这个空节点。这样可以收缩树的大小防止浪费空间。
如果清除子树后,发现跟节点只存在一个自节点那么可以收缩整棵树的大小,减少高度,进一步减少存储数据的量以及索引的节点数目
func (n *Node) delete(ctx context.Context, bs cbor.IpldStore, height int, i uint64) error { subi := i / nodesForHeight(width, height) set, _ := n.getBit(subi) if !set { return &ErrNotFound{i} } if height == 0 { //找到节点,清理该节点 n.expandValues() n.expVals[i] = nil n.clearBit(i) return nil } subn, err := n.loadNode(ctx, bs, subi, false) if err != nil { return err } //递归向下查找 if err := subn.delete(ctx, bs, height-1, i%nodesForHeight(width, height)); err != nil { return err } if subn.empty() { //清理空枝 n.clearBit(subi) n.cache[subi] = nil n.expLinks[subi] = cid.Undef } return nil }
到此,关于“go的amt数组算法怎么用”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。