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
}