关于golang:B树原理以及Go语言实现

B+树介绍

B+树是B树的一种变种，因而若想理解B+树，首先要理解B树的定义。B树又称多路均衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用M示意。个别从查找效率思考，通常要求M>=3。一棵M阶B树，有如下个性：

• 若根节点不是叶子结点，则至多有两棵树。
• 每一个节点最多M棵子树，最多有M-1个关键字。
• 除根节点外，其余的每个分支至多有ceil(M/2)个子树，至多含有ceil(M/2)-1个关键字。
• 每个节点中的关键字都依照大小顺序排列，每个关键字的左子树的所有关键字都小于它，每个关键字的右子树都大于它。
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都雷同。

下图是一个B树的例子：

为了适应磁盘IO拜访的特点以及适应范畴查问的需要，B+树对B树进行了改良。对于一棵m阶的B+树，有如下个性：

• 每个节点至少有M个子树。
• 除根结点外，每个结点至多有ceil(M/2)个子树。
• 结点的子树个数于关键字个数相等。
• 所有的叶子结点中蕴含了全副关键字的信息，及指向含这些关键字记录的指针，且叶子结点自身依关键字的大小自小而大程序链接。
• 所有的非终端结点（非叶子结点）能够看成是索引局部，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

下图是一个B+树的例子：

B+树和B树相比，次要有以下区别：

• 非叶子节点只存储键值信息，数据记录都寄存在叶子节点中。
• 所有叶子节点之间都有一个链指针。
• 非叶子节点的关键字的个数与其子树的个数雷同，不像B树，子树的个数总比关键字个数多1个。

B+树通常用于数据库索引，例如Mysql的InnoDB存储引擎以及MyISAM存储引擎的索引文件中应用的就是B+树。一般来说，数据库的索引都比拟大，不可能全副存储在内存中，因而索引往往以文件的模式存储的磁盘上。零碎从磁盘读取文件到内存时，须要定位到文件所在的地位：文件所在柱面号，磁盘号，扇区号。这个操作时十分耗时的，远高于内存操作。思考到磁盘IO是十分昂扬的操作，操作系统在读取文件时做了一些优化，零碎从磁盘读取文件到内存时是以磁盘块（block）为根本单位的，位于同一个磁盘块中的数据会被一次性读取进去，而不是须要什么取什么。每一次IO读取的数据咱们称之为一页(page)。具体一页有多大数据跟操作系统无关，个别为4k或8k。

因为磁盘IO十分耗时，因而评估一个数据结构作为索引的优劣最重要的指标就是在查找过程中是否可能无效缩小磁盘I/O的操作次数。Mysql抉择应用B+树作为索引文件的数据结构，次要基于B+树的以下特点：

• B+树的磁盘读写代价更低
  
• B+树查问效率更加稳固
  
• B+树便于范畴查问
  <所有叶子节点造成有序链表，对于数据库中频繁应用的范畴查问，B+树有着更高的性能。。

在InnoDB中，表数据文件自身就是按B+树组织的一个索引构造，它应用数据库主键作为Key，叶节点保留了残缺的数据记录。InnoDB中有页（Page）的概念，页是其磁盘治理的最小单位。InnoDB中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K。InnoDB中，B+Tree的高度个别都在2~4层。因为根节点常驻内存的，因而查找某一键值的行记录时最多只须要1~3次磁盘I/O操作。因为InnoDB的数据文件自身要按主键汇集，所以InnoDB要求表必须有主键（MyISAM能够没有），如果没有显式指定，则MySQL零碎会主动抉择一个能够惟一标识数据记录的列作为主键，如果不存在这种列，则MySQL主动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。汇集索引这种实现形式使得按主键的搜寻非常高效，然而辅助索引搜寻须要检索两遍索引：首先检索辅助索引取得主键，而后用主键到主索引中检索取得记录。

B+树中插入数据

在B+树中插入数据时，须要留神以下几点：

• 插入数据时首先定位到数据所在的叶子结点，而后将数据插入到该结点，插入数据后不能毁坏关键字自小而大的排列程序。
• 若插入元素后该节点关键字数目<=阶数M，则间接实现插入操作。
• 若插入的元素为该节点的最大值，则须要批改其父结点中的索引值。
• 若插入元素后该节点关键字数目>阶数M，则须要将该结点决裂为两个结点，关键字的个数别离为：floor((M+1)/2)和ceil((M+1)/2)。
• 若决裂结点后导致父节点的关键字数目>阶数M，则父节点也要进行相应的决裂操作。

数据插入阐明：

• 若被插入关键字所在的结点，其含有关键字数目小于阶数M，则直接插入完结。

下图是插入关键字：15后的后果：

• 若被插入关键字所在的结点，其含有关键字数目等于阶数M，则须要将该结点决裂为两个结点。

上图中插入关键字：9后结点的关键字数量为：4，超过了B+树阶数M，因而须要进行结点决裂操作，决裂后的后果为：

B+树中删除数据

在 B+树中做删除关键字的操作，采取如下的步骤：

• 当删除某结点中最大或者最小的关键字，就会波及到更改其双亲结点始终到根结点中所有索引值的更改。
• 删除关键字后，如果若以后结点中关键字个数小于>=[M/2]，则间接实现删除操作。
• 在删除关键字后，如果导致其结点中关键字个数<[M/2]，若其兄弟结点中含有多余的关键字，能够从兄弟结点中借关键字。
• 在删除关键字后，如果导致其结点中关键字个数<[M/2]，并且其兄弟结点没有多余的关键字，则须要同其兄弟结点进行合并。
• 结点合并后，须要批改父结点的关键字的个数，若父结点的关键字个数<[M/2]，须要按照以上法则进行解决。

数据删除阐明：

• 删除关键字后，如果若以后结点中关键字个数小于>=[M/2]，则间接实现删除操作。
  
  上图中删除关键字：8，删除后的后果如下：
  
• 在删除关键字后，如果导致其结点中关键字个数<[M/2]，若其兄弟结点中含有多余的关键字，能够从兄弟结点中借关键字。
  

上图中删除关键字：21，因为删除后结点只有一个关键字：25<[M/2]，因而须要从兄弟结点中借用一个关键字：17，删除后的后果如下：

• 在删除关键字后，如果导致其结点中关键字个数<[M/2]，并且其兄弟结点没有多余的关键字，则须要同其兄弟结点进行合并。
  
  上图中删除关键字：9，因为删除后结点只有一个关键字：11<[M/2]，并且兄弟结点也没有多余的关键字，因而须要与兄弟结点进行合并，删除后的后果如下：
  

Go语言代码

接下来咱们给出B+树的Go语言的实现，目前代码曾经上传到github中，下载地址

结点的定义

首先给出B+树结点的定义，在此叶子结点与索引结点应用了雷同的数据结构：

type BPItem struct {
    Key     int64
    Val     interface{}
}
type BPNode struct {
    MaxKey    int64
    Nodes     []*BPNode
    Items     []BPItem
    Next     *BPNode
}

其中：

• BPItem用于数据记录。
• MaxKey：用于存储子树的最大关键字
• Nodes：结点的子树（叶子结点的Nodes=nil）
• Items：叶子结点的数据记录（索引结点的Items=nil）
• Next：叶子结点中指向下一个叶子结点，用于实现叶子结点链表

B+树的定义

type BPTree struct {
    mutex      sync.RWMutex
    root      *BPNode
    width     int
    halfw     int

其中：

• root：指向B+树的根结点
• width：用于示意B+树的阶
• halfw：用于[M/2]=ceil(M/2)

B+树的初始化

func NewBPTree(width int) *BPTree {
    if width <3 {
        width = 3
    }
    var bt = &BPTree{}
    bt.root = NewLeafNode(width)
    bt.width = width
    bt.halfw = (bt.width + 1) / 2
    return bt
}

//申请width+1是因为插入时可能临时呈现节点key大于申请width的状况,待前期再决裂解决
func NewLeafNode(width int) *BPNode {
    var node = &BPNode{}
    node.Items = make([]BPItem, width+1)
    node.Items = node.Items[0:0]
    return node
}

B+树的查问

func (t *BPTree) Get(key int64) interface{} {
    t.mutex.Lock()
    defer t.mutex.Unlock()

    node := t.root
    for i := 0; i  0 {
        return nil
    }

    for i := 0; i 

func (t *BPTree) Set(key int64, value interface{}) {
    t.mutex.Lock()
    defer t.mutex.Unlock()
    t.setValue(nil, t.root, key, value)
}
func (t *BPTree) setValue(parent *BPNode, node *BPNode, key int64, value interface{}) {
    for i:=0; i 

func (node *BPNode) setValue(key int64, value interface{}) {
    item := BPItem{key, value}
    num := len(node.Items)
    if num <1 {
        node.Items = append(node.Items, item)
        node.MaxKey = item.Key
        return
    } else if key  node.Items[num-1].Key {
        node.Items = append(node.Items, item)
        node.MaxKey = item.Key
        return
    }

    for i:=0; i  key {
            node.Items = append(node.Items, BPItem{})
            copy(node.Items[i+1:], node.Items[i:])
            node.Items[i] = item
            return
        } else if node.Items[i].Key == key {
            node.Items[i] = item
            return
        }
    }
}

func (t *BPTree) splitNode(node *BPNode) *BPNode {
    if len(node.Nodes) > t.width {
        //创立新结点
        halfw := t.width / 2 + 1
        node2 := NewIndexNode(t.width)
        node2.Nodes = append(node2.Nodes, node.Nodes[halfw : len(node.Nodes)]...)
        node2.MaxKey = node2.Nodes[len(node2.Nodes)-1].MaxKey

        //批改原结点数据
        node.Nodes = node.Nodes[0:halfw]
        node.MaxKey = node.Nodes[len(node.Nodes)-1].MaxKey

        return node2
    } else if len(node.Items) > t.width {
        //创立新结点
        halfw := t.width / 2 + 1
        node2 := NewLeafNode(t.width)
        node2.Items = append(node2.Items, node.Items[halfw: len(node.Items)]...)
        node2.MaxKey = node2.Items[len(node2.Items)-1].Key

        //批改原结点数据
        node.Next = node2
        node.Items = node.Items[0:halfw]
        node.MaxKey = node.Items[len(node.Items)-1].Key

        return node2
    }

    return nil
}

func (t *BPTree) Remove(key int64) {
    t.mutex.Lock()
    defer t.mutex.Unlock()
    t.deleteItem(nil, t.root, key)
}
func (t *BPTree) deleteItem(parent *BPNode, node *BPNode, key int64) {
    for i:=0; i 

func (node *BPNode) deleteItem(key int64) bool {
    num := len(node.Items)
    for i:=0; i  key {
            return false
        } else if node.Items[i].Key == key {
            copy(node.Items[i:], node.Items[i+1:])
            node.Items = node.Items[0:len(node.Items)-1]
            node.MaxKey = node.Items[len(node.Items)-1].Key
            return true
        }
    }
    return false
}

func (t *BPTree) itemMoveOrMerge(parent *BPNode, node *BPNode) {
    //获取兄弟结点
    var node1 *BPNode = nil
    var node2 *BPNode = nil
    for i:=0; i  0 {
                node1 = parent.Nodes[i-1]
            }
            break
        }
    }

    //将左侧结点的记录挪动到删除结点
    if node1 != nil && len(node1.Items) > t.halfw {
        item := node1.Items[len(node1.Items)-1]
        node1.Items = node1.Items[0:len(node1.Items)-1]
        node1.MaxKey = node1.Items[len(node1.Items)-1].Key
        node.Items = append([]BPItem{item}, node.Items...)
        return
    }

    //将右侧结点的记录挪动到删除结点
    if node2 != nil && len(node2.Items) > t.halfw {
        item := node2.Items[0]
        node2.Items = node1.Items[1:]
        node.Items = append(node.Items, item)
        node.MaxKey = node.Items[len(node.Items)-1].Key
        return
    }
    
    //与左侧结点进行合并
    if node1 != nil && len(node1.Items) + len(node.Items) <= t.width {
        node1.Items = append(node1.Items, node.Items...)
        node1.Next = node.Next
        node1.MaxKey = node1.Items[len(node1.Items)-1].Key
        parent.deleteChild(node)
        return
    }

    //与右侧结点进行合并
    if node2 != nil && len(node2.Items) + len(node.Items) <= t.width {
        node.Items = append(node.Items, node2.Items...)
        node.Next = node2.Next
        node.MaxKey = node.Items[len(node.Items)-1].Key
        parent.deleteChild(node2)
        return
    }
}