// search recursively performs a binary search against a given page/node until it finds a given key.// 检索key,有node就走node检索,有page就走page检索func(c*Cursor)search(key[]byte,pgidpgid){p,n:=c.bucket.pageNode(pgid)ifp!=nil&&(p.flags&(branchPageFlag|leafPageFlag))==0{panic(fmt.Sprintf("invalid page type: %d: %x",p.id,p.flags))}e:=elemRef{page:p,node:n}// 记录走过的节点(page,node,index)栈,方便方法之间调用(减少参数)c.stack=append(c.stack,e)// If we're on a leaf page/node then find the specific node.ife.isLeaf(){c.nsearch(key)return}// 有内存node,走node检索,找到对应的节点后,递归进行searchifn!=nil{c.searchNode(key,n)return}// 只有磁盘page,走磁盘page检索,找到对应的节点后,递归进行searchc.searchPage(key,p)}
// put inserts a key/value.func(n*node)put(oldKey,newKey,value[]byte,pgidpgid,flagsuint32){ifpgid>=n.bucket.tx.meta.pgid{panic(fmt.Sprintf("pgid (%d) above high water mark (%d)",pgid,n.bucket.tx.meta.pgid))}elseiflen(oldKey)<=0{panic("put: zero-length old key")}elseiflen(newKey)<=0{panic("put: zero-length new key")}// Find insertion index.index:=sort.Search(len(n.inodes),func(iint)bool{returnbytes.Compare(n.inodes[i].key,oldKey)!=-1})// 二分插入排序,保证整个nodes是有序的// Add capacity and shift nodes if we don't have an exact match and need to insert.exact:=(len(n.inodes)>0&&index<len(n.inodes)&&bytes.Equal(n.inodes[index].key,oldKey))if!exact{n.inodes=append(n.inodes,inode{})copy(n.inodes[index+1:],n.inodes[index:])}inode:=&n.inodes[index]inode.flags=flagsinode.key=newKeyinode.value=valueinode.pgid=pgid_assert(len(inode.key)>0,"put: zero-length inode key")}