BTree源码分析

type BTree struct {
 // BTree的度
 degree int
 // BTree中元素的数量
 length int
 root   *node
 cow    *copyOnWriteContext
}

type node struct {
 items    items
 children children
 cow      *copyOnWriteContext
}

type items []Item

type children []*node

type Item interface {
 Less(than Item) bool
}

func (t *BTree) ReplaceOrInsert(item Item) Item {
 // 检查待插入元素，不能为nil
 if item == nil {
  panic("nil item being added to BTree")
 }
 // part 1
 // 向BTree中首次插入元素，此时BTree中根节点为空，创建一个根节点
 // 并将插入元素加入到根节点
 if t.root == nil {
  t.root = t.cow.newNode()
  t.root.items = append(t.root.items, item)
  t.length++
  return nil
 } else {
  // part 2
  // 检查根节点中元素的数量是否达到最大数量(2*degree-1),如果达到最大数量
  // 则对根节点从中间元素的位置分裂成2个节点，然后创建一个新的根节点，将中间
  // 元素添加到新的根节点中，最后将分裂的两个节点添加到新的根的子节点中，
  // 构成它的左右子节点，此时BTree会长高一层
  t.root = t.root.mutableFor(t.cow)
  // 检查根节点中元素的数量是否达到分裂条件
  if len(t.root.items) >= t.maxItems() {
   // 将根节点分裂成两部分，即将根节点 [first][item2][second]分裂
   // 子节点1 [first]
   // 子节点2 [second]
   item2, second := t.root.split(t.maxItems() / 2)
   // 保存旧根节点到oldroot，此时的oldroot即为上面的first节点的根节点
   oldroot := t.root
   // 新创建一个节点作为根节点
   t.root = t.cow.newNode()
   // 将元素item2加入到新的根节点中
   t.root.items = append(t.root.items, item2)
   // 将first节点和second加入的新的根节点的子节点中
   t.root.children = append(t.root.children, oldroot, second)
  }
 }
 // part 3
 // 真正得进行将元素item加入到BTree中，所有元素的插入都是在叶子节点插入。一路从
 // BTree的根节点向下定位到要插入的叶子的节点位置，在定位的过程中，遇到节点的元素个数
 // 达到最大值(2*degree-1)，则要对该节点进行拆分，并将中间的元素加入到父节点中，即产生
 // 上溢操作
 out := t.root.insert(item, t.maxItems())
 // out为nil,表示当前插入的元素之前不在BTree中
 if out == nil {
  // BTree中元素的数量+1
  t.length++
 }
 // out如果不为空，记录的是之前的旧元素item
 return out
}

func (n *node) insert(item Item, maxItems int) Item {
 // 检查节点n中是否已存在待插入的元素item
 i, found := n.items.find(item)
 // 如果元素已存在，更新item，并返回旧item
 if found {
  out := n.items[i]
  n.items[i] = item
  return out
 }
 // 如果当前的节点n是叶子节点，直接添加item到n中，然后返回
 if len(n.children) == 0 {
  n.items.insertAt(i, item)
  return nil
 }
 // 检查当前节点n的第i个子节点是否需要进行分裂，即检查节点n的child(i)中的元素是否
 // 达到2*degree-1个，如果达到，则对节点child(i)进行分裂，并将child(i)中的中间元素
 // 添加到的它的父节点(即节点n)中。也许有种担心，将中间元素添加节点n中，有可能导致节点n
 // 中的元素超过2*degree-1个，即导致节点n不满足BTree性质。这种情况是不会出现的，因为
 // 整个插入过程是从根节点向下查找并判断节点中元素是否超限的，所以当在处理到节点n的时候，它的
 // 元素个数最大为2*degree-2个，现在向它里面添加一个元素，它能达到的最大值为2*degree-1
 if n.maybeSplitChild(i, maxItems) {
  inTree := n.items[i]
  switch {
  case item.Less(inTree):
   // no change, we want first split node
   // item大小在inTree的左子树中
  case inTree.Less(item):
   i++ // we want second split node
   // item大小在inTree的右子树中
   // 因为child(i)进行了分裂，所以这里i值要加1，表示在分裂的右节点中进行查询
  default:
   // 待插入的元素item在child(i)节点中存在，更新它，并返回旧
   // 元素的值
   out := n.items[i]
   n.items[i] = item
   return out
  }
 }
 // 递归在child(i)节点所在的子树中插入元素item
 return n.mutableChild(i).insert(item, maxItems)
}

// 探测是否要对节点n的孩子节点i进行分裂
func (n *node) maybeSplitChild(i, maxItems int) bool {
 // 检查孩子节点i中的元素数量是否小于2*degree-1,如果小于，不用进行分裂
 if len(n.children[i].items) < maxItems {
  return false
 }
 // 获取节点n的真正孩子节点i
 first := n.mutableChild(i)
 // 对节点first从中间进行分裂成两个节点，节点first和节点second
 item, second := first.split(maxItems / 2)
 // 将孩子节点i中的中间元素添加到它的父节点（节点n）中
 n.items.insertAt(i, item)
 // 将节点second添加到节点n,作为节点n的第i+1个孩子节点
 n.children.insertAt(i+1, second)
 return true
}

// 从BTree中删除给定的元素
func (t *BTree) Delete(item Item) Item {
 return t.deleteItem(item, removeItem)
}

func (t *BTree) deleteItem(item Item, typ toRemove) Item {
 // 如果树为空或者根节点中没有元素，直接返回，因为这种情况待删除的元素肯定不存在
 if t.root == nil || len(t.root.items) == 0 {
  return nil
 }
 t.root = t.root.mutableFor(t.cow)
 // 从根节点开始查找待删除的元素并删除它，这个过程是一个递归查找删除的过程
 out := t.root.remove(item, t.minItems(), typ)
 // 因为删除的过程可能进行节点的合并，会导致树的高度减少一层，这里处理的就是这种情况
 // 根节点已经没有元素了，但还有孩子节点，此时t.root.children[0]会成为根节点，
 // 并且t.root.children中也只要一个节点
 if len(t.root.items) == 0 && len(t.root.children) > 0 {
  oldroot := t.root
  t.root = t.root.children[0]
  // 释放掉旧的根节点
  t.cow.freeNode(oldroot)
 }
 if out != nil {
  // out不为空，说明待删除的元素在BTree中存在并删除了，元素的数量减1
  t.length--
 }
 return out
}

func (n *node) remove(item Item, minItems int, typ toRemove) Item {
 var i int
 var found bool
 switch typ {
 case removeMax:
  // n为叶子节点，直接删除节点n的items里面的最后一个元素
  // 不用担心删除n的item会导致该节点中元素为空或者不满足BTree最少元素个数
  // ,不存在这种情况，删完之后节点n的最少元素个数为degree-1
  if len(n.children) == 0 {
   return n.items.pop()
  }
  // i为要进行处理的孩子节点下标，最右边的子节点
  i = len(n.items)
 case removeMin:
  // n为叶子节点，直接删除节点n的items里面的第一个元素
  if len(n.children) == 0 {
   return n.items.removeAt(0)
  }
  // 继续向下，最左边的子节点
  i = 0
 case removeItem:
  // 查找当前节点n的元素中是否存在item
  i, found = n.items.find(item)
  // 递归出口之一：已经查询到了叶子节点
  if len(n.children) == 0 {
   // 查询到了叶子节点，并且元素item在叶子节点中，直接删除
   if found {
    return n.items.removeAt(i)
   }
   // 查询到了叶子节点，但是没有查到，递归也结束，返回nil
   return nil
  }
 default:
  panic("invalid type")
 }
 
 // 根据节点n的孩子节点i中的元素个数情况，有两种处理逻辑：
 // 逻辑1，孩子节点i的元素个数<=minItems=degree-1,此时需要对孩子节点i中的元素进行
 // 补充，补充方式是从它的兄弟节点借，或者进行节点合并
 if len(n.children[i].items) <= minItems {
  return n.growChildAndRemove(i, item, minItems, typ)
 }
 
 // 逻辑2：孩子节点i中的元素个数还是够的，这时的处理逻辑根据元素item是否在节点n中分两种情况
 // 情况1，item在节点n中找到了，即found为true,将孩子节点中右子树中最右边的叶子节点中的最后一个
 // 元素覆盖掉节点n中的i号元素，并将叶子节点的元素删除
 child := n.mutableChild(i)
 if found {
  out := n.items[i]
  // 即找到节点n的最大前驱节点中的最大元素赋值给n.items[i]，并将叶子节点中的元素删除
  n.items[i] = child.remove(nil, minItems, removeMax)
  return out
 }
 // 情况2 在孩子节点child中继续递归查找&删除
 return child.remove(item, minItems, typ)
}

func (n *node) growChildAndRemove(i int, item Item, minItems int, typ toRemove) Item {
 // 孩子节点i有左兄弟，并且孩子节点i的左边的一个兄弟节点元素是够的，从它里面将最大的元素借走
 if i > 0 && len(n.children[i-1].items) > minItems {
  // 真正的孩子节点i
  child := n.mutableChild(i)
  // 真正的孩子节点i-1
  stealFrom := n.mutableChild(i - 1)
  // 孩子节点i-1中的最大元素（也是items切片中最后一个元素）被移除
  stolenItem := stealFrom.items.pop()
  // 将节点n中的元素items[i-1]插入到孩子节点i的最左边
  child.items.insertAt(0, n.items[i-1])
  // 将孩子节点i-1中的最大的元素赋值给节点n中的元素items[i-1]
  n.items[i-1] = stolenItem
  // 处理stealFrom的孩子节点，因为stealFrom节点中的最后一个元素pop出去了
  // 此时它的孩子节点数量比它的元素多2个，不满足BTree性质，所以需要将它的最后一个
  // 孩子节点pop出去，然后放入到child节点中，并作为它最左边的孩子节点。因为child节点
  // 刚好插入了一个元素，它缺少1个孩子节点。这样处理之后，完美的构成了BTree
  if len(stealFrom.children) > 0 {
   child.children.insertAt(0, stealFrom.children.pop())
  }
 } else if i < len(n.items) && len(n.children[i+1].items) > minItems {
  // 孩子节点i有右兄弟，并且第一个右兄弟中的元素是够的，从它里面借一个元素
  // 真正的孩子节点i
  child := n.mutableChild(i)
  // 真正的孩子节点i+1
  stealFrom := n.mutableChild(i + 1)
  // 孩子节点i+1中的最小元素（也是items切片中第一个元素）被移除
  stolenItem := stealFrom.items.removeAt(0)
  // 将节点n中的元素i添加到孩子节点i中
  child.items = append(child.items, n.items[i])
  // 将从右兄弟借走的元素赋值给节点n中元素i的位置
  n.items[i] = stolenItem
  // 处理stealFrom的孩子节点，因为stealFrom节点中的第一个元素pop出去了
  // 此时它的孩子节点数量比它的元素多2个，不满足BTree性质，所以需要将它的第一个
  // 孩子节点pop出去，然后放入到child节点中，并作为它最右边的孩子节点。因为child节点
  // 刚好插入了一个元素，它缺少1个孩子节点。
  if len(stealFrom.children) > 0 {
   child.children = append(child.children, stealFrom.children.removeAt(0))
  }
 } else {
  // 走到这里，说明前面两种情况都不满足，即child(i)节点的左右兄弟节点都没有足够的元素可以借
  // 这个时候的处理办法是对孩子节点进行合并，不用担心，合并之后节点的个数不会超过2*degree-1

  // 合并的是两个节点是child(i)和child(i+1)，也就是将child和它的右兄弟进行合并

  // 处理特殊情况，当前的child已经是节点n的最右的孩子节点，所以child是没有右兄弟了
  // 这时候将i-1, 实际变成了将child和它的左兄弟合并。这里将i-1使得后面的处理变得统一
  if i >= len(n.items) {
   i--
  }
  // 真正的孩子节点
  child := n.mutableChild(i)
  // 将节点n中位置i的元素移走
  mergeItem := n.items.removeAt(i)
  // 因为节点n中位置i中的元素移走了，所以节点n的孩子节点也要减少1个，
  // 将节点n中位置i+1中的孩子节点移走
  mergeChild := n.children.removeAt(i + 1)
  // 将节点n中移走的元素添加到孩子节点child中
  child.items = append(child.items, mergeItem)
  // 将mergeChild中的元素添加到child中，因为是mergeChild合并到child
  child.items = append(child.items, mergeChild.items...)
  // 将mergeChild中的子节点添加到child.children中
  child.children = append(child.children, mergeChild.children...)
  // mergeChild的元素和子节点信息已合并到了child中，此时mergeChild节点可以释放了
  n.cow.freeNode(mergeChild)
 }
 // 上面处理的是对child节点的合并，还没有做删除item的操作，下面才进行删除操作
 // 注意这里一定是从节点n开始remove操作，因为上面的合并操作会导致节点n中的元素发生变化
 // 从它的子节点进行remove会漏掉元素
 return n.remove(item, minItems, typ)
}

func (t *BTree) Get(key Item) Item {
 if t.root == nil {
  return nil
 }
 return t.root.get(key)
}

// 查找给定的元素是否在node中存在，会递归查询node的孩子节点
func (n *node) get(key Item) Item {
 i, found := n.items.find(key)
 if found {
       // 找到了 直接返回
  return n.items[i]
 } else if len(n.children) > 0 {
        // 没有找到 递归查询子节点
  return n.children[i].get(key)
 }
    // 走到这里，已经走到了叶子节点，并且没有查到，返回nil
 return nil
}

type BTree struct {
 // BTree的度
 degree int
 // BTree中元素的数量
 length int
 root   *node
 // 默认的空闲node数量为32个
 cow    *copyOnWriteContext
}

type copyOnWriteContext struct {
 freelist *FreeList
}

type FreeList struct {
 mu       sync.Mutex
 // freelist 默认缓存空闲node的切片大小为32
 freelist []*node
}

func New(degree int) *BTree {
 return NewWithFreeList(degree, NewFreeList(DefaultFreeListSize))
}

func NewWithFreeList(degree int, f *FreeList) *BTree {
 if degree <= 1 {
  panic("bad degree")
 }
 return &BTree{
  degree: degree,
  cow:    &copyOnWriteContext{freelist: f},
 }
}

func (c *copyOnWriteContext) newNode() (n *node) {
 n = c.freelist.newNode()
 n.cow = c
 return
}

func (f *FreeList) newNode() (n *node) {
 ...
 // index<0 表示空闲缓存中没有node了，这个时候new一个
 if index < 0 {
  f.mu.Unlock()
  return new(node)
 }
 ...
    // 从freelist中获取
 return
}

func (c *copyOnWriteContext) freeNode(n *node) freeType {
 if n.cow == c {
  ...
        // 将node n放回freelist
  if c.freelist.freeNode(n) {
   return ftStored
  } else {
   return ftFreelistFull
  }
 } else {
  return ftNotOwned
 }
}

func (f *FreeList) freeNode(n *node) (out bool) {
 f.mu.Lock()
 if len(f.freelist) < cap(f.freelist) {
  f.freelist = append(f.freelist, n)
  out = true
 }
 f.mu.Unlock()
 return
}

func (t *BTree) Clone() (t2 *BTree) {
 // 产生两个cow对象，cow1和cow2的对象地址是不同的
 cow1, cow2 := *t.cow, *t.cow
 // 拷贝对象t，也就是第二颗BTree对象
 out := *t
 // 更新旧BTree的cow1
 t.cow = &cow1
 // 更新新BTree的cow2
 out.cow = &cow2
 return &out
}