BTree源码分析

数据小冰

发布于 2022-08-15 15:01:12

6700

发布于 2022-08-15 15:01:12

本文是介绍BTree文章的下篇，在BTree实现原理上篇主要介绍实现原理，下篇主要介绍btree源码实现。

BTree数据结构

BTree是一种多路平衡树，多路通过度(degree)来体现，树通过记录根节点来表达。所以BTree结构必须包含描述树的度和根节点信息。下面是BTree结构体定义，结构体中的degree和root字段，正是我们这里分析的BTree必须有的基本信息,此外还定义了一个length字段，它表示BTree中有多少个元素，cow字段起辅助优化作用，用于在多颗BTree中达到节点node复用的作用，减少gc开销。

BTree结构体中的degree(度)描述了节点中元素的最大数量，也描述了节点的最大子节点的个数。对于一个度为n的BTree,BTree中节点的元素个数最多为2n-1个，除根节点外，每个节点的最少元素个数为n-1个。同时也说明，节点中子节点的个数最多为2n个，除根节点之外，每个节点的子节点个数最少为n个。

BTree结构

BTree结构体定义

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

node描述BTree中节点的信息，因为每个节点包含元素信息和子节点的信息，这是节点的最基本的信息，下面的node结构体定义中，items表示元素信息，children表示子节点的信息。

items是一个别名类型，它的实际类型为Item的切片。类似的，children是*node的切片。cow是优化使用的，包含写时复制的上下文信息。详细的作用在分析BTree的Clone时介绍。items和children都是切片的别名，这样做是为了代码的封装处理。

节点node结构

node结构体定义

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

type items []Item

type children []*node

Item描述的是BTree中node中的元素信息，对于btree库的实现者来说，要容纳任意的元素类型，如果是我们来定义Item类型，因为interface{}能包罗万象，容纳任意类型的类型，所以会将Item定义为空接口类型。但btree库中将Item定义为含有Less方法的interface类型，所以Item不仅是interface类型，而是一个实现Less方法的接口类型。这样在BTree的创建、查找和删除等操作时，对使用者来说也更方便。

BTree中的元素Item定义

type Item interface {
 Less(than Item) bool
}

BTree库函数

BTree库函数是btree包提供给外部使用的API接口，也就是上面BTree结构体提供给外部的方法以及BTree的构造函数。这里做了一个汇总说明。

方法名称	功能说明
New(degree int) *BTree	BTree构造函数，传入BTree的度值
NewWithFreeList(degree int, f FreeList) BTree	BTree构造函数，需要传入度值和一个free list参数
NewFreeList(size int) *FreeList	free list构造函数
(t BTree) Clone() (t2 BTree)	对BTree进行克隆，得到一颗新的BTree,与被克隆的BTree共享node节点
(t *BTree) ReplaceOrInsert(item Item)	向BTree中插入元素，如果插入的元素已存在，则更新
(t *BTree) Delete(item Item)	从BTree中删除给定的元素
(t *BTree) DeleteMin() Item	删除BTree中最小的元素
(t *BTree) DeleteMax() Item	删除BTree中最大的元素
(t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator)	对元素的大小在范围[greaterOrEqual,lessThan)内的元素按升序进行遍历处理
(t *BTree) AscendLessThan(pivot Item, iterator ItemIterator)	对元素的大小在范围[first,pivot)内的元素按升序进行遍历处理
(t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator)	对元素的大小在范围[pivot,last]内的元素按升序进行遍历处理
(t *BTree) Ascend(iterator ItemIterator)	对元素的大小在范围[first,last]内的元素按升序进行遍历处理
(t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator)	对元素的大小在范围[lessOrEqual, greaterThan)内的元素按降序进行遍历处理
(t *BTree) DescendLessOrEqual(pivot Item, iterator ItemIterator)	对元素的大小在范围[pivot, first]内的元素按降序进行遍历处理
(t *BTree) DescendGreaterThan(pivot Item, iterator ItemIterator)	对元素的大小在范围[last, pivot)内的元素按降序进行遍历处理
(t *BTree) Descend(iterator ItemIterator)	对元素的大小在范围[last, first]内的元素按降序进行遍历处理
(t *BTree) Get(key Item) Item	返回BTree中元素为key的元素
(t *BTree) Min() Item	返回BTree中最小的元素
(t *BTree) Max() Item	返回BTree中最大的元素
(t *BTree) Has(key Item) bool	检查BTree中是否存在元素为key的元素
(t *BTree) Len() int	返回BTree中元素的数量
(t *BTree) Clear(addNodesToFreelist bool)	清空BTree中的节点，如果传入参数为true，会将节点加入到free list中

BTree基本操作实现

插入、删除和查询是BTree最基本的操作，在BTree实现原理文章中介绍了它们的实现原理，此处将从源码的角度分析这几种操作的实现。

插入

向BTree中插入元素的逻辑实现方法为ReplaceOrInsert，该方法只有一个入参，即待插入的元素，返回值为一个Item类型，如果待插入的元素已在BTree中，则返回的值为旧元素，如果不存在，返回的Item为nil.

整个插入逻辑有点复杂，可以分成3部分来理解。第一部分逻辑处理的是首次向BTree中插入元素的情况，这个时候BTree的根节点还不存在，先创建一个根节点，然后将待插入的元素item添加到根节点中，更新下BTree中的元素的数量t.length,整个处理已结束可以返回了。

第二部分，也就是下面代码part 2处的逻辑块。检查根节点的元素数量是否达到最大值(2*degree-1)，如果达到最大值，则需要对根节点进行分裂成两部分，同时需要创建一个新的节点作为根节点，树会长高一层。待分裂节点的中间元素移动到新的根节点中，最后将分裂的两个节点添加到新的根节点中，作为它的左右子节点。

最后的第三部分是插入的核心逻辑，先说明一点，「向BTree插入元素都是在叶子节点插入」.一路从BTree的根节点向下定位到要插入的叶子的节点位置，在定位的过程中，遇到节点的元素个数达到最大值(2*degree-1)，则要对该节点进行拆分，并将中间的元素加入到父节点中，即产生上溢操作. 插入实现在insert方法中，见下面的详细分析。

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
}

插入操作insert函数是一个递归调用，所以一开始逻辑处理递归结束的情况。这里的结束情况为待插入的元素在当前的节点n中或当前的节点n已是叶子节点。如果待插入的元素已在节点n中，更新item并返回旧item. 如果当前的节点n是叶子节点，则直接将item加入到n中。剩下的就是递归调用的逻辑，从内部节点不断递归到叶子节点。递归的过程中要处理一种情况，就是当前节点的孩子节点i，也就是item将要插入的子树，存在着节点元素大于等于2*degree-1的情况，这种情况下插入item后会导致节点的元素个数超标，所以提前判断当节点的元素个数>=2*degreee-1时，对该节点进行分裂，将分裂节点的中间元素移动到父节点中。

也许有种担心，将中间元素添加节点n中，有可能导致节点n中的元素超过2*degree-1个，即导致节点n不满足BTree性质。这种情况是不会出现的，因为整个插入过程是从根节点向下查找并判断节点中元素是否超限的，所以当在处理到节点n的时候，它的元素个数最大为2*degree-2个，现在向它里面添加一个元素，它能达到的最大值为2*degree-1。

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)
}

maybeSplitChild探测是否要对节点n的孩子节点i进行分裂

// 探测是否要对节点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
}

删除

删除操作对外的接口是Delete方法，传入一个待删除的元素item, 返回值也是一个Item类型，如果待删除的元素在BTree中存在，则返回它，否则返回值为nil.

删除的内部实现是deleteItem方法，它包含了删除BTree中最小元素、最大元素和任意元素的逻辑。整个deleteItem主要处理3部分逻辑。

第一部分是特殊情况检查，BTree为空或没有元素，这种情况直接返回。
第二部分也是最核心的部分，执行真正的删除操作，调用的是node的remove方法，remove在下面详细分析，删除操作之后要检查根节点中的元素是否存在，因为在删除的过程中，可能有节点合并，导致树降低一层。
第三部分更新树中元素的个数。

// 从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
}

remove处理删除最小元素、最大元素和任意元素的三种情况的逻辑，处理过程比较复杂。先来说删除最小元素和最大元素这两种简单的情况。

最小的元素在最左边的叶子节点中，并且是节点中第一个元素，所以一路向左下发，定位到最左边的叶子节点，将其第一个元素删除，对应的是下面的case removeMin逻辑。

类似的，最大的元素在最右边叶子节点中，并且是它的最后一个元素。定位到最右边的叶子节点之后将其删除即可，对应到下面的case removeMax逻辑。

看了下面的删除最小和最大元素操作，也许有同学有疑问？怎么没有考虑删除叶子节点中元素被删除之后可能导致节点数量不满足节点最小数量限制，甚至出现叶子节点中元素为空的情况。不用担心，这种情况是不存在的，remove在访问节点的过程，会判断当前节点n的孩子child(i)节点中元素是否不够的情况，如果不够，则会进行处理。具体处理在下面的growChildAndRemove中讲。所以这里将叶子节点删除一个元素之后，它里面还是有元素的，删除之后最小的数量为degree-1，还是满足BTree定义的。

remove操作是一个递归调用，递归的出口只有两种情况，一是在递归访问节点的过程中查到了待删除的元素，将其从节点中删除。二是待删除的元素在BTree中不存在，这种情况会一直查找到叶子节点，返回nil.

从节点中删除元素，可能会打破BTree性质，要进行调整处理。根据节点n的孩子节点i中的元素个数情况，存在着两种情况：

情况1 孩子节点i的元素个数<=minItems=degree-1,此时需要对孩子节点i中的元素进行补充，补充方式是从它的兄弟节点借，或者进行节点合并，这部分处理在growChildAndRemove函数，后面会详细分析该逻辑。
情况2 孩子节点i中的元素个数还是够的，这时的处理逻辑根据元素item是否在节点n中分两种情况：2.1 item在节点n中找到了，即found为true,将孩子节点中右子树中最右边的叶子节点中的最后一个元素覆盖掉节点n中的i号元素，并将叶子节点的元素删除 2.2 在孩子节点child中继续递归查找&删除

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)
}

growChildAndRemove方法处理节点n的child(i)中元素不够的情况，处理的思路有两个，从它兄弟节点借或者对节点进行合并。下面实现中有3个if分支，前两个分支是从兄弟节点借，分为从左兄弟借或右兄弟借两种情况，最后一个是对节点进行合并，因为左右兄弟节点都没有足够的元素。

从左兄弟节点借：孩子节点i有左兄弟，并且孩子节点i的左边的一个兄弟节点元素是够的，从它里面将最大的元素借走。将孩子节点i-1中的最大的元素赋值给节点n中的元素items[i-1]，将节点n中的元素items[i-1]插入到孩子节点i的最左边
从右兄弟节点借：孩子节点i有右兄弟，并且第一个右兄弟中的元素是够的，从它里面借一个元素。将节点n中的元素i添加到孩子节点i中，将从右兄弟借走的元素赋值给节点n中元素i的位置
对节点进行合并：节点n的child(i)节点的左右兄弟节点都没有足够的元素可以借，合并的是两个节点是child(i)和child(i+1)。处理特殊情况，当前的child已经是节点n的最右的孩子节点，所以child是没有右兄弟了。详细的合并逻辑见下面的源码注解，已经说的很详细了

从右兄弟节点借

对节点进行合并

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)
}

查询

查询的操作Get方法处理逻辑很简单，查询的过程是一个递归的过程，直到走到叶子节点，还没有查到，返回nil, 如果在内部节点中查询到了元素，则直接返回。

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
}

BTree优化技巧

btree是一个生产包，它对GC和并发读写操作方面做了很多优化，我们可以从中学习它的优化思路。总结起来，btree的优化技巧有两点：

针对GC问题,通过缓存，能够对节点进行复用，降低GC开销，这里的缓存就是代码中的freelist
对于并发读写，通过写时复制，降低内存的开销，多颗BTree可以共享节点node,在写时才进行复制，保证互相不干扰

下面结合代码来分析优化是怎么做的，前面分析过BTree结构定义，这里在拿出来分析, 我们现在主要关注它的cow字段，这个字段的类型是一个copyOnWriteContext类型的指针。copyOnWriteContext结构中只有一个字段freelist, 它的类型是FreeList指针。FreeList中的freeelist是一个node指针的切片，mu是用来在并发情况下保护freelist的。

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
}

上述的copyOnWriteContext结构图形结构是长下面这样。

btree包提供了两种BTree对象的两种构造方法，其中一种方式需要传入给FreeList类型的对象，这样可以在多颗BTree上共享FreeList对象。

通过New函数产生的BTree的cow中的freelist是不共享的，内部会new一个FreeList对象，通过NewWithFreeList产生的BTree,需要外部传入一个FreeList, 这样传入相同的FreeList得到的BTree是共享的。

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},
 }
}

还有一点需要说明，无论是通过New还是NewWithFreeList产生的BTree,BTree中的cow值都是不同的，也就是每个BTree中根节点的cow都是不同的。这样可以通过根节点的cow来区分是不是同一颗BTree.

除了BTree结构体，node结构定义中也有一个cow字段。对应BTree中的node节点来说，它的cow值与BTree中的cow是一致的，都指向同一个copyOnWriteContext对象，表示它们都属于同一颗BTree。

FreeList结构中的freelist用于缓存释放的node节点，下次申请node的时候，优先从freelist中获取。

申请node时优先从freelist中获取

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
}

删除的时候将node返回freelist

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
}

通过cow实现写时复制，多个BTree可以共享节点，有修改或删除操作才对节点进行拷贝，在副本上进行修改或删除。

通过Clone操作，可以获取两颗一模一样的BTree,这两颗BTree共享节点信息，实际只保存了一份节点，节省空间。注意下面的源码，更新了旧BTree t的cow，这里不更新可以吗？不可以，因为后续对t的修改或删除操作，会影响t2,所以这里给它赋值一个新的cow，用于区分。结合下面这张图理解起来很容易理解。

克隆前

克隆后

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
}

本文参与?腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-12，如有侵权请联系?cloudcommunity@tencent.com 删除

node.js