Boltdb学习笔记之二--数据结构

type nodes []*node
// inode represents an internal node inside of a node.
// It can be used to point to elements in a page or point
// to an element which hasn't been added to a page yet.
type inode struct {
 flags uint32
 pgid  pgid
 key   []byte
 value []byte
}
type inodes []inode
// node represents an in-memory, deserialized page.
type node struct {
 bucket     *Bucket
 isLeaf     bool
 unbalanced bool
 spilled    bool
 key        []byte
 pgid       pgid
 parent     *node
 children   nodes
 inodes     inodes
}

for i, item := range n.inodes {
  _assert(len(item.key) > 0, "write: zero-length inode key")
  // Write the page element.
  if n.isLeaf {
   elem := p.leafPageElement(uint16(i))
   elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
   elem.flags = item.flags
   elem.ksize = uint32(len(item.key))
   elem.vsize = uint32(len(item.value))
  } else {
   elem := p.branchPageElement(uint16(i))
   elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
   elem.ksize = uint32(len(item.key))
   elem.pgid = item.pgid
   _assert(elem.pgid != p.id, "write: circular dependency occurred")
  }
        // If the length of key+value is larger than the max allocation size
  // then we need to reallocate the byte array pointer.
  //
  // See: https://github.com/boltdb/bolt/pull/335
  klen, vlen := len(item.key), len(item.value)
  if len(b) < klen+vlen {
   b = (*[maxAllocSize]byte)(unsafe.Pointer(&b[0]))[:]
  }
  // Write data for the element to the end of the page.
  copy(b[0:], item.key)
  b = b[klen:]
  copy(b[0:], item.value)
  b = b[vlen:]
 }

// read initializes the node from a page.
func (n *node) read(p *page) {
 n.pgid = p.id
 n.isLeaf = ((p.flags & leafPageFlag) != 0)
 n.inodes = make(inodes, int(p.count))
 for i := 0; i < int(p.count); i++ {
  inode := &n.inodes[i]
  if n.isLeaf {
   elem := p.leafPageElement(uint16(i))
   inode.flags = elem.flags
   inode.key = elem.key()
   inode.value = elem.value()
  } else {
   elem := p.branchPageElement(uint16(i))
   inode.pgid = elem.pgid
   inode.key = elem.key()
  }
  _assert(len(inode.key) > 0, "read: zero-length inode key")
 }
 // Save first key so we can find the node in the parent when we spill.
 if len(n.inodes) > 0 {
  n.key = n.inodes[0].key
  _assert(len(n.key) > 0, "read: zero-length node key")
 } else {
  n.key = nil
 }
}

// put inserts a key/value.
func (n *node) put(oldKey, newKey, value []byte, pgid pgid, flags uint32) {
    ...
 // Find insertion index.
 index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, oldKey) != -1 })
 // 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 = flags
 inode.key = newKey
 inode.value = value
 inode.pgid = pgid
 _assert(len(inode.key) > 0, "put: zero-length inode key")
}

// del removes a key from the node.
func (n *node) del(key []byte) {
 // Find index of key.
 index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, key) != -1 })
 // Exit if the key isn't found.
 if index >= len(n.inodes) || !bytes.Equal(n.inodes[index].key, key) {
  return
 }
 // Delete inode from the node.
 n.inodes = append(n.inodes[:index], n.inodes[index+1:]...)
 // Mark the node as needing rebalancing.
 n.unbalanced = true
}

// bucket represents the on-file representation of a bucket.
// This is stored as the "value" of a bucket key. If the bucket is small enough,
// then its root page can be stored inline in the "value", after the bucket
// header. In the case of inline buckets, the "root" will be 0.
type bucket struct {
    root     pgid   // page id of the bucket's root-level page
    sequence uint64 // monotonically incrementing, used by NextSequence()
}

// Bucket represents a collection of key/value pairs inside the database.
type Bucket struct {
    *bucket
    tx       *Tx                // the associated transaction
    buckets  map[string]*Bucket // subbucket cache
    page     *page              // inline page reference
    rootNode *node              // materialized node for the root page.
    nodes    map[pgid]*node     // node cache
    // Sets the threshold for filling nodes when they split. By default,
    // the bucket will fill to 50% but it can be useful to increase this
    // amount if you know that your write workloads are mostly append-only.
    //
    // This is non-persisted across transactions so it must be set in every Tx.
    FillPercent float64
}

// Get retrieves the value for a key in the bucket.
// Returns a nil value if the key does not exist or if the key is a nested bucket.
// The returned value is only valid for the life of the transaction.
func (b *Bucket) Get(key []byte) []byte {
 k, v, flags := b.Cursor().seek(key)
 // Return nil if this is a bucket.
 if (flags & bucketLeafFlag) != 0 {
  return nil
 }
 // If our target node isn't the same key as what's passed in then return nil.
 if !bytes.Equal(key, k) {
  return nil
 }
 return v
}

// seek moves the cursor to a given key and returns it.
// If the key does not exist then the next key is used.
func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
 _assert(c.bucket.tx.db != nil, "tx closed")
 // Start from root page/node and traverse to correct page.
 c.stack = c.stack[:0]
 c.search(seek, c.bucket.root)
 ref := &c.stack[len(c.stack)-1]
 // If the cursor is pointing to the end of page/node then return nil.
 if ref.index >= ref.count() {
  return nil, nil, 0
 }
 // If this is a bucket then return a nil value.
 return c.keyValue()
}

// search recursively performs a binary search against a given page/node until it finds a given key.
func (c *Cursor) search(key []byte, pgid pgid) {
 p, n := c.bucket.pageNode(pgid)
 if p != nil && (p.flags&(branchPageFlag|leafPageFlag)) == 0 {
  panic(fmt.Sprintf("invalid page type: %d: %x", p.id, p.flags))
 }
 e := elemRef{page: p, node: n}
 c.stack = append(c.stack, e)
 // If we're on a leaf page/node then find the specific node.
 if e.isLeaf() {
  c.nsearch(key)
  return
 }
 if n != nil {
  c.searchNode(key, n)
  return
 }
 c.searchPage(key, p)
}

func (c *Cursor) searchNode(key []byte, n *node) {
 var exact bool
 index := sort.Search(len(n.inodes), func(i int) bool {
  // TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
  // sort.Search() finds the lowest index where f() != -1 but we need the highest index.
  ret := bytes.Compare(n.inodes[i].key, key)
  if ret == 0 {
   exact = true
  }
  return ret != -1
 })
 if !exact && index > 0 {
  index--
 }
 c.stack[len(c.stack)-1].index = index
 // Recursively search to the next page.
 c.search(key, n.inodes[index].pgid)
}

// Put sets the value for a key in the bucket.
// If the key exist then its previous value will be overwritten.
// Supplied value must remain valid for the life of the transaction.
// Returns an error if the bucket was created from a read-only transaction, if the key is blank, if the key is too large, or if the value is too large.
func (b *Bucket) Put(key []byte, value []byte) error {
 if b.tx.db == nil {
  return ErrTxClosed
 } else if !b.Writable() {
  return ErrTxNotWritable
 } else if len(key) == 0 {
  return ErrKeyRequired
 } else if len(key) > MaxKeySize {
  return ErrKeyTooLarge
 } else if int64(len(value)) > MaxValueSize {
  return ErrValueTooLarge
 }
 // Move cursor to correct position.
 c := b.Cursor()
 k, _, flags := c.seek(key)
 // Return an error if there is an existing key with a bucket value.
 if bytes.Equal(key, k) && (flags&bucketLeafFlag) != 0 {
  return ErrIncompatibleValue
 }
 // Insert into node.
 key = cloneBytes(key)
 c.node().put(key, key, value, 0, 0)
 return nil
}

// Delete removes a key from the bucket.
// If the key does not exist then nothing is done and a nil error is returned.
// Returns an error if the bucket was created from a read-only transaction.
func (b *Bucket) Delete(key []byte) error {
 if b.tx.db == nil {
  return ErrTxClosed
 } else if !b.Writable() {
  return ErrTxNotWritable
 }
 // Move cursor to correct position.
 c := b.Cursor()
 _, _, flags := c.seek(key)
 // Return an error if there is already existing bucket value.
 if (flags & bucketLeafFlag) != 0 {
  return ErrIncompatibleValue
 }
 // Delete the node if we have a matching key.
 c.node().del(key)
 return nil
}

// spill writes all the nodes for this bucket to dirty pages.
func (b *Bucket) spill() error {
 // Spill all child buckets first.
 for name, child := range b.buckets {
  // If the child bucket is small enough and it has no child buckets then
  // write it inline into the parent bucket's page. Otherwise spill it
  // like a normal bucket and make the parent value a pointer to the page.
  var value []byte
  if child.inlineable() {
   child.free()
   value = child.write()
  } else {
   if err := child.spill(); err != nil {
    return err
   }
   // Update the child bucket header in this bucket.
   value = make([]byte, unsafe.Sizeof(bucket{}))
   var bucket = (*bucket)(unsafe.Pointer(&value[0]))
   *bucket = *child.bucket
  }
  // Skip writing the bucket if there are no materialized nodes.
  if child.rootNode == nil {
   continue
  }
  // Update parent node.
  var c = b.Cursor()
  k, _, flags := c.seek([]byte(name))
  if !bytes.Equal([]byte(name), k) {
   panic(fmt.Sprintf("misplaced bucket header: %x -> %x", []byte(name), k))
  }
  if flags&bucketLeafFlag == 0 {
   panic(fmt.Sprintf("unexpected bucket header flag: %x", flags))
  }
  c.node().put([]byte(name), []byte(name), value, 0, bucketLeafFlag)
 }
 // Ignore if there's not a materialized root node.
 if b.rootNode == nil {
  return nil
 }
 // Spill nodes.
 if err := b.rootNode.spill(); err != nil {
  return err
 }
 b.rootNode = b.rootNode.root()
 // Update the root node for this bucket.
 if b.rootNode.pgid >= b.tx.meta.pgid {
  panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", b.rootNode.pgid, b.tx.meta.pgid))
 }
 b.root = b.rootNode.pgid
 return nil
}

// rebalance attempts to balance all nodes.
func (b *Bucket) rebalance() {
 for _, n := range b.nodes {
  n.rebalance()
 }
 for _, child := range b.buckets {
  child.rebalance()
 }
}

// CreateBucket creates a new bucket at the given key and returns the new bucket.
// Returns an error if the key already exists, if the bucket name is blank, or if the bucket name is too long.
// The bucket instance is only valid for the lifetime of the transaction.
func (b *Bucket) CreateBucket(key []byte) (*Bucket, error) {
 if b.tx.db == nil {
  return nil, ErrTxClosed
 } else if !b.tx.writable {
  return nil, ErrTxNotWritable
 } else if len(key) == 0 {
  return nil, ErrBucketNameRequired
 }
 // Move cursor to correct position.
 c := b.Cursor()
 k, _, flags := c.seek(key)
 // Return an error if there is an existing key.
 if bytes.Equal(key, k) {
  if (flags & bucketLeafFlag) != 0 {
   return nil, ErrBucketExists
  }
  return nil, ErrIncompatibleValue
 }
 // Create empty, inline bucket.
 var bucket = Bucket{
  bucket:      &bucket{},
  rootNode:    &node{isLeaf: true},
  FillPercent: DefaultFillPercent,
 }
 var value = bucket.write()
 // Insert into node.
 key = cloneBytes(key)
 c.node().put(key, key, value, 0, bucketLeafFlag)
 // Since subbuckets are not allowed on inline buckets, we need to
 // dereference the inline page, if it exists. This will cause the bucket
 // to be treated as a regular, non-inline bucket for the rest of the tx.
 b.page = nil
 return b.Bucket(key), nil
}

// Bucket retrieves a nested bucket by name.
// Returns nil if the bucket does not exist.
// The bucket instance is only valid for the lifetime of the transaction.
func (b *Bucket) Bucket(name []byte) *Bucket {
 if b.buckets != nil {
  if child := b.buckets[string(name)]; child != nil {
   return child
  }
 }
 // Move cursor to key.
 c := b.Cursor()
 k, v, flags := c.seek(name)
 // Return nil if the key doesn't exist or it is not a bucket.
 if !bytes.Equal(name, k) || (flags&bucketLeafFlag) == 0 {
  return nil
 }
 // Otherwise create a bucket and cache it.
 var child = b.openBucket(v)
 if b.buckets != nil {
  b.buckets[string(name)] = child
 }
 return child
}