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

31次阅读

共计 7780 个字符，预计需要花费 20 分钟才能阅读完成。

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+ 树的外部结点只有关键字，没有数据，一个结点能够包容更多的关键字。查问时一次性读入内存中的关键字也就越多，相对来说 I / O 读写次数也就升高了。
  • 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 < len(node.Nodes); i++ {if key <= node.Nodes[i].MaxKey {node = node.Nodes[i]
            i = 0
        }
    }

    // 没有达到叶子结点
    if len(node.Nodes) > 0 {return nil}

    for i := 0; i < len(node.Items); i++ {if node.Items[i].Key == key {return node.Items[i].Val
        }
    }
    return nil
}

B+ 树的插入操作

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 < len(node.Nodes); i++ {if key <= node.Nodes[i].MaxKey || i== len(node.Nodes)-1 {t.setValue(node, node.Nodes[i], key, value)
            break
        }
    }

    // 叶子结点，增加数据
    if len(node.Nodes) < 1 {node.setValue(key, value)
    }

    // 结点决裂
    node_new := t.splitNode(node)
    if node_new != nil {
        // 若父结点不存在，则创立一个父节点
        if parent == nil {parent = NewIndexNode(t.width)
            parent.addChild(node)
            t.root = parent
        }
        // 增加结点到父亲结点
        parent.addChild(node_new)
    }
}

代码中应用递归调用实现数据的插入。插入时首先定位到叶子结点，而后调用 BPNode.setValue()来设置关键字：

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[0].Key {node.Items = append([]BPItem{item}, node.Items...)
        return
    } else if key > node.Items[num-1].Key {node.Items = append(node.Items, item)
        node.MaxKey = item.Key
        return
    }

    for i:=0; i < num; i++ {if node.Items[i].Key > 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
        }
    }
}

增加关键字后若数量超过：BPTree.width，则须要调用 BPNode.splitNode()来进行结点决裂解决：

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
}

B+ 树的删除操作

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 < len(node.Nodes); i++ {if key <= node.Nodes[i].MaxKey {t.deleteItem(node, node.Nodes[i], key)
            break
        }
    }

    if  len(node.Nodes) < 1 {
        // 删除记录后若结点的子项 <m/2，则从兄弟结点挪动记录，或者合并结点
        node.deleteItem(key)
        if len(node.Items) < t.halfw {t.itemMoveOrMerge(parent, node)
        }
    } else {
        // 若结点的子项 <m/2，则从兄弟结点挪动记录，或者合并结点
        node.MaxKey = node.Nodes[len(node.Nodes)-1].MaxKey
        if len(node.Nodes) < t.halfw {t.childMoveOrMerge(parent, node)
        }
    }
}

代码中应用递归调用实现删除操作。删除时首先定位到叶子结点，若找到则调用 BPNode.deleteItem()来删除关键字：

func (node *BPNode) deleteItem(key int64) bool {num := len(node.Items)
    for i:=0; i < num; i++ {if node.Items[i].Key > 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
}

删除关键字后，若关键字的数量小于 BPTree.halfw，则须要调用BPNode.itemMoveOrMerge() 函数。
BPNode.itemMoveOrMerge()函数首先获取兄弟结点，并判断是否能够借用关键字，若能够进行关键字借用，否则与兄弟结点进行合并：

func (t *BPTree) itemMoveOrMerge(parent *BPNode, node *BPNode) {
    // 获取兄弟结点
    var node1 *BPNode = nil
    var node2 *BPNode = nil
    for i:=0; i < len(parent.Nodes); i++ {if parent.Nodes[i] == node {if i < len(parent.Nodes)-1 {node2 = parent.Nodes[i+1]
            } else if 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
    }
}

正文完
golang
发表至： golang
2022-04-13
 0
关于golang:有趣的面试题Go语言中nil的比较结果
关于golang:Golang力扣Leetcode-205同构字符串哈希
关于golang:WebAssembly-Go-系列1什么是-WebAssembly-和-Go-语言示例
28-学习-Go-协程互斥锁和读写锁