我们一起再聊聊B-Tree的Golang实现

这是B-Tree合集的第二部分。在这一部分会实现基本的数据结构和Search。

创新互联专注于网站建设|网站建设维护|优化|托管以及网络推广，积累了大量的网站设计与制作经验，为许多企业提供了网站定制设计服务，案例作品覆盖公路钻孔机等行业。能根据企业所处的行业与销售的产品，结合品牌形象的塑造，量身建设品质网站。

基本数据结构

根据Part1介绍的B-Tree的属性，我们可以建立node和tree两个基本的数据结构

type BTreeNode struct {
  keys []int        // An array of keys
  t    int          // Minimum degree
  c    []*BTreeNode // An array of child pointers
  n    int          // Current number of keys
  leaf bool         // Is true when node is leaf. Otherwise false
}

type BTree struct {
  root *BTreeNode // Pointer to root node
  t    int        // Minimum degree
}

// Constructor for BTreeNode
func NewBTreeNode(t int, leaf bool) *BTreeNode {
  return &BTreeNode{
    keys: make([]int, t<<1-1),
    t:    t,
    c:    make([]*BTreeNode, t<<1),
    leaf: leaf,
  }
}

// Constructor (Initializes tree as empty)
func NewBTree(t int) *BTree {
  return &BTree{
    t: t,
  }
}

Search

比如要在下面这个B树中找120

那么从Part1可知，我们都会从root出发，所以有下面3步即可找到120

可见，可以用下面的伪代码来描述Search方法

对于红框里面的，意思是找第一个大于等于k的键index，但是伪代码用了顺序查找的方法，即O(N)。从Part1可知，node中的元素是从小到大排列的，所以我们可以用二分的方式优化。

// find the index of the first key which is greater or equal to k
func findGE(s []int, left, right, k int) int {
  if left <= right {
    mid := left + (right-left)>>1

    if k == s[mid] {
      return mid
    } else if k > s[mid] {
      return findGE(s, mid+1, right, k)
    } else {
      return findGE(s, left, mid-1, k)
    }
  }

  return left
}

下面是Search的代码

func (n *BTreeNode) search(k int) *BTreeNode {
  i := findGE(n.keys, 0, n.n-1, k)

  if n.keys[i] == k {
    return n
  }
  if n.leaf {
    return nil
  }
  return n.c[i].search(k)
}

func (t *BTree) Search(k int) *BTreeNode {
  if t.root != nil {
    return t.root.search(k)
  }

  return nil
}

在下次的Part3中，将实现B-Tree的Insert。

本文标题：我们一起再聊聊B-Tree的Golang实现
文章起源：http://www.csdahua.cn/qtweb/news10/26960.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网