前面我們了解了Transaction的定義和它的創(chuàng)建及初始化過(guò)程，其中涉及到了根Bucket的創(chuàng)建。Transaction主要是對(duì)Bucket進(jìn)行創(chuàng)建、查找、刪除等操作，Bucket可以嵌套形成樹(shù)結(jié)構(gòu)，故Transaction對(duì)Bucket的操作均從根Bucket開(kāi)始進(jìn)行的。BoltDB中所有的K/V記錄或者page均通過(guò)Bucket組織起來(lái)，且一個(gè)Bucket內(nèi)的所有node形成一顆B+Tree。我們先來(lái)看看Bucket的定義:
//boltdb/bolt/bucket.go
// Bucket represents a collection of key/value pairs inside the database.
type Bucket struct {
*bucket
tx *Tx // the associated transaction
buckets map[string]*Bucket // subbucket cache
page *page // inline page reference
rootNode *node // materialized node for the root page.
nodes map[pgid]*node // node cache
// Sets the threshold for filling nodes when they split. By default,
// the bucket will fill to 50% but it can be useful to increase this
// amount if you know that your write workloads are mostly append-only.
//
// This is non-persisted across transactions so it must be set in every Tx.
FillPercent float64
}
// bucket represents the on-file representation of a bucket.
// This is stored as the "value" of a bucket key. If the bucket is small enough,
// then its root page can be stored inline in the "value", after the bucket
// header. In the case of inline buckets, the "root" will be 0.
type bucket struct {
root pgid // page id of the bucket's root-level page
sequence uint64 // monotonically incrementing, used by NextSequence()
}
Bucket的各字段定義如下:
- *bucket: Bucket的頭，其定義中的root是指Bucket根節(jié)點(diǎn)的頁(yè)號(hào)，sequence是一個(gè)序列號(hào)，可以用于Bucket的序號(hào)生成器。這里稍微解釋一下，Go中類(lèi)型定義中未指明成員名稱(chēng)，則該成員是一個(gè)隱含成員，成員的成員以及與其綁定的方法可以被外層類(lèi)型的變量直接訪(fǎng)問(wèn)或者調(diào)用，相當(dāng)于通過(guò)組合的方式讓外層內(nèi)型"繼承"了隱含成員的類(lèi)型;
- tx: 當(dāng)前Bucket所屬的Transaction。請(qǐng)注意，Transaction與Bucket均是動(dòng)態(tài)的概念，即內(nèi)存中的對(duì)象，Bucket最終表示為BoltDB中的K/V記錄，這將在后面看到;
- page: 內(nèi)置(inline)Bucket的頁(yè)引用，內(nèi)置Bucket只有一個(gè)節(jié)點(diǎn)，即它的根節(jié)點(diǎn)，且節(jié)點(diǎn)不存在獨(dú)立的頁(yè)面中，而是作為Bucket的Value存在父Bucket所在頁(yè)上，頁(yè)引用就是指向Value中的內(nèi)置頁(yè)，我們將在分析Bucket創(chuàng)建時(shí)進(jìn)一步說(shuō)明;
- rootNode: Bucket的根節(jié)點(diǎn)，也是對(duì)應(yīng)B+Tree的根節(jié)點(diǎn);
- nodes: Bucket中的node集合;
- FillPercent: Bucket中節(jié)點(diǎn)的填充百分比(或者占空比)。該值與B+Tree中節(jié)點(diǎn)的分裂有關(guān)系，當(dāng)節(jié)點(diǎn)中Key的個(gè)數(shù)或者size超過(guò)整個(gè)node容量的某個(gè)百分比后，節(jié)點(diǎn)必須分裂為兩個(gè)節(jié)點(diǎn)，這是為了防止B+Tree中插入K/V時(shí)引發(fā)頻繁的再平衡操作，所以注釋中提到只有當(dāng)確定大數(shù)多寫(xiě)入操作是向尾添加時(shí)，這個(gè)值調(diào)大才有幫助。該值的默認(rèn)值是50%;
介紹完Bucket的定義后，為了讓大家對(duì)Bucket及它在整個(gè)DB中的作用有個(gè)直觀的認(rèn)識(shí)，我們先來(lái)看一看BoltDB的畫(huà)像:
圖中展示了5個(gè)Bucket: root Bucket、BucketA、BucketB、BucketAA及BucketBB。除root Bucket外，其余4個(gè)Bucket均由粉色區(qū)域標(biāo)注。BucketA與BucketB是root Bucket的子Bucket，它們嵌套在root Bucket中; BucketAA是BucketA的嵌套子Bucket，BucketBB是BucketB的嵌套子Bucket，而且BucketBB是一個(gè)內(nèi)置Bucket。嵌套Bucket形成父子關(guān)系，從而所有Bucket形成樹(shù)結(jié)構(gòu)，通過(guò)根Bucket可以遍歷所有子Bucket，但是請(qǐng)注意，Bucket之間的樹(shù)結(jié)構(gòu)并不是B+Tree，而是一個(gè)邏輯樹(shù)結(jié)構(gòu)，如BucketBB是BucketB的子Bucket，但并不是說(shuō)BucketBB所在的節(jié)點(diǎn)就是BucketB所在節(jié)點(diǎn)的子節(jié)點(diǎn)。從圖中也可以看出，我們?cè)?a href="http://www.itdecent.cn/p/65980834ce88" target="_blank">《區(qū)塊的持久化之BoltDB(二)》介紹的Transaction初始化時(shí)，從meta中讀取根Bucket頭就是為了找到根Bucket所在頁(yè)，進(jìn)而從頁(yè)中讀出根Bucket的根節(jié)點(diǎn)。
每一個(gè)Bucket都對(duì)應(yīng)一顆B+Tree，Bucket結(jié)構(gòu)中的rootNode指向根節(jié)點(diǎn)。需要說(shuō)明的是，B+Tree的有些定義有爭(zhēng)議: 如通過(guò)階還是度來(lái)標(biāo)識(shí)，度是指節(jié)點(diǎn)中最大或者最小的Key的數(shù)量還是子節(jié)點(diǎn)的數(shù)量，以及內(nèi)節(jié)點(diǎn)或根節(jié)點(diǎn)中Pointer的數(shù)量是Key的數(shù)量加1還是等于Key的數(shù)量等等。在BoltDB中，內(nèi)節(jié)點(diǎn)或根節(jié)點(diǎn)中Pointer的數(shù)量等于Key的數(shù)量，即子節(jié)點(diǎn)的個(gè)數(shù)與Key的數(shù)量相等。在我們的表述中，為了避免混淆，統(tǒng)一通過(guò)如下四個(gè)參數(shù)描述B+Tree: (每節(jié)點(diǎn)中Key的數(shù)量最大值，每節(jié)點(diǎn)中Pointer的數(shù)量最大值，每節(jié)點(diǎn)中Key的數(shù)量最小值，節(jié)點(diǎn)填充率)。對(duì)應(yīng)地，我們圖中的B+Tree的參數(shù)即是(3, 3, 1, 100%)，為了便于說(shuō)明，圖中節(jié)點(diǎn)的填充率為100%，且一個(gè)節(jié)點(diǎn)中最多只有3個(gè)K/V對(duì)；請(qǐng)注意，BoltDB的實(shí)現(xiàn)上默認(rèn)節(jié)點(diǎn)填充率是50%，而且節(jié)點(diǎn)中Key的數(shù)量的最大值和最小值是根據(jù)頁(yè)大小與Key的size來(lái)動(dòng)態(tài)決定的。對(duì)于不熟悉B+Tree的讀者，可以對(duì)照BucketAA對(duì)應(yīng)的B+Tree(圖中左下角)來(lái)理解一下。為了便于說(shuō)明有序關(guān)系，樹(shù)中的Key均通過(guò)數(shù)字表示。從圖中可以看出，實(shí)際的K/V對(duì)均保存在葉子節(jié)點(diǎn)中，節(jié)點(diǎn)中的K/V對(duì)按Key的順序有序排列。父節(jié)點(diǎn)中只有Key和Pointer，沒(méi)有Value，Pointer指向子節(jié)點(diǎn)，且Pointer對(duì)應(yīng)的Key是它指向的子節(jié)點(diǎn)中最小Key值。父節(jié)點(diǎn)中的Key也按順序排列，所以其子節(jié)點(diǎn)之間也是按順序排列的，所有子節(jié)點(diǎn)會(huì)形成有序鏈表。圖中的B+Tree上，當(dāng)我們要查找Key為6的記錄時(shí)，先從左至右查找(或者通過(guò)二分法查找)根節(jié)點(diǎn)的Key值，發(fā)現(xiàn)6大于4且小于7，那么可以肯定Key為6的記錄位于Key為4對(duì)應(yīng)的子節(jié)點(diǎn)上，因此進(jìn)入對(duì)應(yīng)的子節(jié)點(diǎn)查找，按相同的查找方法(從左至右或者二分法查找)查找Key為6的記錄，最多經(jīng)過(guò)三次比較后就可以找到。同時(shí)，在B+Tree中，一個(gè)節(jié)點(diǎn)中的Key的數(shù)量如果大于節(jié)點(diǎn)Key數(shù)量的最大值 x 填充率的話(huà)，節(jié)點(diǎn)會(huì)分裂(split)成兩個(gè)節(jié)點(diǎn)，并向父節(jié)點(diǎn)添加一個(gè)Key和Pointer，添加后如果父節(jié)點(diǎn)也需要分裂的話(huà)那就進(jìn)行分裂直到根節(jié)點(diǎn)；為了盡量減少節(jié)點(diǎn)分裂的情況，可以對(duì)B+Tree進(jìn)行旋轉(zhuǎn)(rotation)或者再平衡(rebalance)：如果一個(gè)節(jié)點(diǎn)中的Key的數(shù)量小于設(shè)定的節(jié)點(diǎn)Key數(shù)量的最小值的話(huà)，那就將其兄弟節(jié)點(diǎn)中的Key移動(dòng)到該節(jié)點(diǎn)，移動(dòng)后產(chǎn)生的空節(jié)點(diǎn)將被刪除，直到所有節(jié)點(diǎn)滿(mǎn)足Key數(shù)量大于節(jié)點(diǎn)Key數(shù)量最小值。
如果被B+Tree的描述弄得有點(diǎn)頭暈的話(huà)，上面的圖我們先放一放，這里只關(guān)注Bucket的結(jié)構(gòu)和B+Tree的大致結(jié)構(gòu)即可，我們后面還會(huì)解釋該圖。接下來(lái)，我們繼續(xù)從《區(qū)塊的持久化之BoltDB(一)》中給的BoltDB典型應(yīng)用示例中的tx.CreatBucket()入手來(lái)介紹Bucket的創(chuàng)建過(guò)程:
//boltdb/bolt/tx.go
// CreateBucket creates a new bucket.
// Returns an error if the bucket already exists, if the bucket name is blank, or if the bucket name is too long.
// The bucket instance is only valid for the lifetime of the transaction.
func (tx *Tx) CreateBucket(name []byte) (*Bucket, error) {
return tx.root.CreateBucket(name)
}
它實(shí)際上是通過(guò)tx的根Bucket來(lái)創(chuàng)建新Bucket的:
//boltdb/bolt/bucket.go
// CreateBucket creates a new bucket at the given key and returns the new bucket.
// Returns an error if the key already exists, if the bucket name is blank, or if the bucket name is too long.
// The bucket instance is only valid for the lifetime of the transaction.
func (b *Bucket) CreateBucket(key []byte) (*Bucket, error) {
......
// Move cursor to correct position.
c := b.Cursor() (1)
k, _, flags := c.seek(key) (2)
......
// Create empty, inline bucket.
var bucket = Bucket{ (3)
bucket: &bucket{},
rootNode: &node{isLeaf: true},
FillPercent: DefaultFillPercent,
}
var value = bucket.write() (4)
// Insert into node.
key = cloneBytes(key) (5)
c.node().put(key, key, value, 0, bucketLeafFlag) (6)
// Since subbuckets are not allowed on inline buckets, we need to
// dereference the inline page, if it exists. This will cause the bucket
// to be treated as a regular, non-inline bucket for the rest of the tx.
b.page = nil (7)
return b.Bucket(key), nil (8)
}
在CreateBucket()中:
- 代碼(1)處為當(dāng)前Bucket創(chuàng)建游標(biāo);
- 代碼(2)處在當(dāng)前Bucket中查找key并移動(dòng)游標(biāo)，確定其應(yīng)該插入的位置;
- 代碼(3)處創(chuàng)建一個(gè)空的內(nèi)置Bucket;
- 代碼(4)處將剛創(chuàng)建的Bucket序列化成byte slice，以作為與key對(duì)應(yīng)的value插入B+Tree；
- 代碼(5)處對(duì)key進(jìn)行深度拷貝以防它引用的byte slice被回收;
- 代碼(6)處將代表子Bucket的K/V插入到游標(biāo)位置，其中Key是子Bucket的名字，Value是子Bucket的序列化結(jié)果;
- 代碼(7)處將當(dāng)前Bucket的page字段置空，因?yàn)楫?dāng)前Bucket包含了剛創(chuàng)建的子Bucket，它不會(huì)是內(nèi)置Bucket;
- 代碼(8)處通過(guò)b.Bucket()方法按子Bucket的名字查找子Bucket并返回結(jié)果。請(qǐng)注意，這里并沒(méi)有將剛創(chuàng)建的子Bucket直接返回而是通過(guò)查找的方式返回，大家可以想一想為什么？
上述代碼涉及到了Bucket的游標(biāo)Cursor，為了理解Bucket中的B+Tree的查找過(guò)程，我們先來(lái)看一看Cursor的定義:
//boltdb/bolt/cursor.go
// Cursor represents an iterator that can traverse over all key/value pairs in a bucket in sorted order.
// Cursors see nested buckets with value == nil.
// Cursors can be obtained from a transaction and are valid as long as the transaction is open.
//
// Keys and values returned from the cursor are only valid for the life of the transaction.
//
// Changing data while traversing with a cursor may cause it to be invalidated
// and return unexpected keys and/or values. You must reposition your cursor
// after mutating data.
type Cursor struct {
bucket *Bucket
stack []elemRef
}
......
// elemRef represents a reference to an element on a given page/node.
type elemRef struct {
page *page
node *node
index int
}
Cursor的各字段意義如下:
- bucket: 要搜索的Bucket的引用;
- stack: 它是一個(gè)slice，其中的元素為elemRef，用于記錄游標(biāo)的搜索路徑，最后一個(gè)元素指向游標(biāo)當(dāng)前位置;
elemRef的各字段意義是:
- page: elemRef所代表的page的引用;
- node：elemRef所代碼的node的引用;
- index：page或node中元素的索引;
elemRef實(shí)際上指向B+Tree上的一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)有可能已經(jīng)實(shí)例化成node，也有可能是未實(shí)例化的page。我們前面提到過(guò)，Bucket是內(nèi)存中的動(dòng)態(tài)對(duì)象，它緩存了node。Cursor在遍歷B+Tree時(shí)，如果節(jié)點(diǎn)已經(jīng)實(shí)例化成node，則elemRef中的node字段指向該node，page字段為空；如果節(jié)點(diǎn)是未實(shí)例化的page，則elemRef中的page字段指向該page，node字段為空。elemRef通過(guò)page或者node指向B+Tree的一個(gè)節(jié)點(diǎn)，通過(guò)index進(jìn)一步指向節(jié)點(diǎn)中的K/V對(duì)。Cursor在B+Tree上的移動(dòng)過(guò)程就是將elemRef添加或者移除出stack的過(guò)程。
前面我們介紹過(guò)page的定義，現(xiàn)在我們看看node的定義:
//boltdb/bolt/node.go
// node represents an in-memory, deserialized page.
type node struct {
bucket *Bucket
isLeaf bool
unbalanced bool
spilled bool
key []byte
pgid pgid
parent *node
children nodes
inodes inodes
}
......
// inode represents an internal node inside of a node.
// It can be used to point to elements in a page or point
// to an element which hasn't been added to a page yet.
type inode struct {
flags uint32
pgid pgid
key []byte
value []byte
}
type inodes []inode
node中各字段意義如下:
- bucket：指向node所屬的Bucket;
- isLeaf: 當(dāng)前node是否是一個(gè)葉子節(jié)點(diǎn)，與page中的flags對(duì)應(yīng);
- unbalanced: 指示當(dāng)前node是否需要再平衡，如果unbalanced為true，則需要對(duì)它進(jìn)行重平衡；當(dāng)節(jié)點(diǎn)中有K/V對(duì)被刪除時(shí)，該值設(shè)為true;
- spilled: 指示當(dāng)前node是否已經(jīng)溢出(spill)，node溢出是指當(dāng)node的size超過(guò)頁(yè)大小，即一頁(yè)無(wú)法存node中所有K/V對(duì)時(shí)，節(jié)點(diǎn)會(huì)分裂成多個(gè)node，以保證每個(gè)node的size小于頁(yè)大小，分裂后產(chǎn)生新的node會(huì)增加父node的size，故父node也可能需要分裂；已經(jīng)溢出過(guò)的node不需要再分裂;
- key: node的key或名字，它是node中第1個(gè)K/V對(duì)的key;
- pgid: 與node對(duì)應(yīng)的頁(yè)框的頁(yè)號(hào);
- parent: 父節(jié)點(diǎn)的引用，根節(jié)點(diǎn)的parent是空;
- children: 當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn);
- inodes: 一個(gè)inode的slice，記錄當(dāng)前node中的K/V;
inode中各字段的意義是:
- flags: 指明該K/V對(duì)是否代表一個(gè)Bucket，如果是Bucket，則其值為1，否則為0;
- pgid: 根節(jié)點(diǎn)或內(nèi)節(jié)點(diǎn)的子節(jié)點(diǎn)的pgid，可以理解為Pointer，請(qǐng)注意，葉子節(jié)點(diǎn)中該值無(wú)意義;
- key：K/V對(duì)的Key;
- value: K/V對(duì)的Value，請(qǐng)注意，非葉子節(jié)點(diǎn)中該值無(wú)意義;
在《區(qū)塊的持久化之BoltDB(二)》中，我們介紹過(guò)node的序列化過(guò)程，即write(p *page)方法，為了進(jìn)一步理解node各字段及其與page的對(duì)應(yīng)關(guān)系，我們來(lái)看看它的反序列化方法read(p *page)：
//boltdb/bolt/node.go
// read initializes the node from a page.
func (n *node) read(p *page) {
n.pgid = p.id
n.isLeaf = ((p.flags & leafPageFlag) != 0)
n.inodes = make(inodes, int(p.count))
for i := 0; i < int(p.count); i++ {
inode := &n.inodes[i]
if n.isLeaf {
elem := p.leafPageElement(uint16(i))
inode.flags = elem.flags
inode.key = elem.key()
inode.value = elem.value()
} else {
elem := p.branchPageElement(uint16(i))
inode.pgid = elem.pgid
inode.key = elem.key()
}
_assert(len(inode.key) > 0, "read: zero-length inode key")
}
// Save first key so we can find the node in the parent when we spill.
if len(n.inodes) > 0 {
n.key = n.inodes[0].key
_assert(len(n.key) > 0, "read: zero-length node key")
} else {
n.key = nil
}
}
node的實(shí)例化過(guò)程為:
- node的pgid設(shè)為page的pgid;
- node的isLeaf字段由page的flags決定，如果page是一個(gè)leaf page，則node的isLeaf為true;
- 創(chuàng)建inodes，其容量由page中元素個(gè)數(shù)決定;
- 接著，向inodes中填充inode。對(duì)于leaf page，inode的flags即為page中元素的flags，key和value分別為page中元素對(duì)應(yīng)的Key和Value；對(duì)于branch page，inode的pgid即為page中元素的pgid，即子節(jié)點(diǎn)的頁(yè)號(hào)，key為page元素對(duì)應(yīng)的Key。node中的inode與page中的leafPageElement或branchPageElement一一對(duì)應(yīng)，可以參考前文中的頁(yè)磁盤(pán)布局圖來(lái)理解inode與elemements的對(duì)應(yīng)關(guān)系;
- 最后，將node的key設(shè)為其中第一個(gè)inode的key;
了解了Cursor及node的定義后，我們接著來(lái)看看CreateBucket()代碼(2)處查找過(guò)程:
//boltdb/bolt/cursor.go
func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
_assert(c.bucket.tx.db != nil, "tx closed")
// Start from root page/node and traverse to correct page.
c.stack = c.stack[:0]
c.search(seek, c.bucket.root)
ref := &c.stack[len(c.stack)-1]
// If the cursor is pointing to the end of page/node then return nil.
if ref.index >= ref.count() {
return nil, nil, 0
}
// If this is a bucket then return a nil value.
return c.keyValue()
}
主要是兩個(gè)步驟:
- 通過(guò)清空stack，將游標(biāo)復(fù)位;
- 調(diào)用search方法從Bucket的根節(jié)點(diǎn)開(kāi)始查找;
我們來(lái)看看search方法:
//boltdb/bolt/cursor.go
// search recursively performs a binary search against a given page/node until it finds a given key.
func (c *Cursor) search(key []byte, pgid pgid) {
p, n := c.bucket.pageNode(pgid)
if p != nil && (p.flags&(branchPageFlag|leafPageFlag)) == 0 {
panic(fmt.Sprintf("invalid page type: %d: %x", p.id, p.flags))
}
e := elemRef{page: p, node: n}
c.stack = append(c.stack, e)
// If we're on a leaf page/node then find the specific node.
if e.isLeaf() {
c.nsearch(key) (1)
return
}
if n != nil {
c.searchNode(key, n) (2)
return
}
c.searchPage(key, p) (3)
}
在search中:
- 通過(guò)Bucket的pageNode()方法根據(jù)pgid找到緩存在Bucket中的node或者還未實(shí)例化的page;
- 創(chuàng)建一個(gè)elemRef對(duì)象，它指向pgid指定的B+Tree節(jié)點(diǎn)，index為0;
- 將剛創(chuàng)建的elemRef對(duì)象添加到stack的尾部，實(shí)現(xiàn)將Cursor移動(dòng)到相應(yīng)的B+Tree節(jié)點(diǎn);
- 如果游標(biāo)指向葉子節(jié)點(diǎn)，則代碼(1)處將開(kāi)始在節(jié)點(diǎn)內(nèi)部查找;
- 如果游標(biāo)指向根節(jié)點(diǎn)或者內(nèi)節(jié)點(diǎn)，且pgid有對(duì)應(yīng)的node對(duì)象，則代碼(3)處開(kāi)始在非葉子節(jié)點(diǎn)中查找，以確定子節(jié)點(diǎn)并進(jìn)行遞歸查找;
- 如果游標(biāo)指向根節(jié)點(diǎn)或者內(nèi)節(jié)點(diǎn)，且pgid沒(méi)有對(duì)應(yīng)的node，只能從page中直接讀branchPageElement，由代碼(4)處開(kāi)始在非葉子節(jié)點(diǎn)中查找，以確定子節(jié)點(diǎn)并進(jìn)行遞歸查找;
Bucket的pageNode()方法的思想是: 從Bucket緩存的nodes中查找對(duì)應(yīng)pgid的node，若有則返回node，page為空；若未找到，再?gòu)腂ucket所屬的Transaction申請(qǐng)過(guò)的page的集合(Tx的pages字段)中查找，有則返回該page，node為空；若Transaction中的page緩存中仍然沒(méi)有，則直接從DB的內(nèi)存映射中查找該頁(yè)，并返回?？傊琾ageNode()就是根據(jù)pgid找到node或者page。
接下來(lái)我們來(lái)分析c.searchNode(key, n)的過(guò)程，c.searchPage(key, p)的過(guò)程與之相似，我們就不作專(zhuān)門(mén)分析了，讀者可以自行分析。
//boltdb/bolt/cursor.go
func (c *Cursor) searchNode(key []byte, n *node) {
var exact bool
index := sort.Search(len(n.inodes), func(i int) bool {
// TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
// sort.Search() finds the lowest index where f() != -1 but we need the highest index.
ret := bytes.Compare(n.inodes[i].key, key)
if ret == 0 {
exact = true
}
return ret != -1
})
if !exact && index > 0 {
index--
}
c.stack[len(c.stack)-1].index = index
// Recursively search to the next page.
c.search(key, n.inodes[index].pgid)
}
在searchNode()中:
- 對(duì)節(jié)點(diǎn)中inodes進(jìn)行有序查找(Go中sort.Search()使用二分法查找)，結(jié)果要么是正好找到key，即exact=true且ret=0；要么是找到比key大的最小inode(即ret=1)或者所有inodes的key均小于目標(biāo)key;
- 如果查找結(jié)果是上述的第二情況，則將結(jié)果索引值減1，因?yàn)橛檎业膋ey肯定位于前一個(gè)Pointer對(duì)應(yīng)的子節(jié)點(diǎn)或子樹(shù)中，可以對(duì)照我們前面舉的BucketAA的例子進(jìn)行理解;
- 將stack中的最后一個(gè)elemRef元素中的index置為查找結(jié)果索引值，即將游標(biāo)移動(dòng)到所指節(jié)點(diǎn)中具體的inode處;
- 從inode記錄的pgid(可以理解為Pointer)對(duì)應(yīng)的子節(jié)點(diǎn)處開(kāi)始遞歸查找;
遞歸調(diào)用的結(jié)束條件是游標(biāo)最終移動(dòng)到一個(gè)葉子節(jié)點(diǎn)處，進(jìn)入c.nsearch(key)過(guò)程:
//boltdb/bolt/cursor.go
// nsearch searches the leaf node on the top of the stack for a key.
func (c *Cursor) nsearch(key []byte) {
e := &c.stack[len(c.stack)-1]
p, n := e.page, e.node
// If we have a node then search its inodes.
if n != nil {
index := sort.Search(len(n.inodes), func(i int) bool {
return bytes.Compare(n.inodes[i].key, key) != -1
})
e.index = index
return
}
// If we have a page then search its leaf elements.
inodes := p.leafPageElements()
index := sort.Search(int(p.count), func(i int) bool {
return bytes.Compare(inodes[i].key(), key) != -1
})
e.index = index
}
在nsearch()中:
- 解出游標(biāo)指向節(jié)點(diǎn)的node或者page;
- 如果是node，則在node內(nèi)進(jìn)行有序查找，結(jié)果為正好找到key或者未找到，未找到時(shí)index位于節(jié)點(diǎn)結(jié)尾處;
- 如果是page，則在page內(nèi)進(jìn)行有序查找，結(jié)果也是正好找到key或者未找到，未找到時(shí)index位于節(jié)點(diǎn)結(jié)尾于;
- 將當(dāng)前游標(biāo)元素的index置為剛剛得到的查找結(jié)果索引值，即把游標(biāo)移動(dòng)到key所在節(jié)點(diǎn)的具體inode處或者結(jié)尾處;
到此，我們就了解了Bucket通過(guò)Cursor進(jìn)行查找的過(guò)程，我們回頭看看seek()方法，在查找結(jié)束后，如果未找到key，即key指向葉子結(jié)點(diǎn)的結(jié)尾處，則它返回空；如果找到則返回K/V對(duì)。需要注意的是，在再次調(diào)用Cursor的seek()方法移動(dòng)游標(biāo)之前，游標(biāo)一直位于上次seek()調(diào)用后的位置。
我們?cè)倩氐皆贑reateBucket()的實(shí)現(xiàn)中，其中代碼(3)處創(chuàng)建了一個(gè)內(nèi)置的子Bucket，它的Bucket頭bucket中的root為0，接著代碼(3)處通過(guò)Bucket的write()方法將內(nèi)置Bucket序列化，我們可以通過(guò)它了解內(nèi)置Bucket是如何作為Value存于頁(yè)框上的:
//boltdb/bolt/bucket.go
// write allocates and writes a bucket to a byte slice.
func (b *Bucket) write() []byte {
// Allocate the appropriate size.
var n = b.rootNode
var value = make([]byte, bucketHeaderSize+n.size())
// Write a bucket header.
var bucket = (*bucket)(unsafe.Pointer(&value[0]))
*bucket = *b.bucket
// Convert byte slice to a fake page and write the root node.
var p = (*page)(unsafe.Pointer(&value[bucketHeaderSize]))
n.write(p)
return value
}
從實(shí)現(xiàn)上看，內(nèi)置Bucket就是將Bucket頭和其根節(jié)點(diǎn)作為Value存于頁(yè)框上，而其頭中字段均為0。接著，CreateBucket()中代碼(6)處將剛創(chuàng)建的子Bucket插入游標(biāo)位置，我們來(lái)看看其中的c.node()調(diào)用:
//boltdb/bolt/cursor.go
// node returns the node that the cursor is currently positioned on.
func (c *Cursor) node() *node {
_assert(len(c.stack) > 0, "accessing a node with a zero-length cursor stack")
// If the top of the stack is a leaf node then just return it.
if ref := &c.stack[len(c.stack)-1]; ref.node != nil && ref.isLeaf() {
return ref.node
}
// Start from root and traverse down the hierarchy.
var n = c.stack[0].node
if n == nil {
n = c.bucket.node(c.stack[0].page.id, nil)
}
for _, ref := range c.stack[:len(c.stack)-1] {
_assert(!n.isLeaf, "expected branch node")
n = n.childAt(int(ref.index))
}
_assert(n.isLeaf, "expected leaf node")
return n
}
它的基本思路是: 如果當(dāng)前游標(biāo)指向了一個(gè)葉子節(jié)點(diǎn)，且節(jié)點(diǎn)已經(jīng)實(shí)例化為node，則直接返回該node；否則，從根節(jié)點(diǎn)處沿Cursor的查找路徑將沿途的所有節(jié)點(diǎn)中未實(shí)例化的節(jié)點(diǎn)實(shí)例化成node，并返回最后節(jié)點(diǎn)的node。實(shí)際上最后的節(jié)點(diǎn)總是葉子節(jié)點(diǎn)，因?yàn)锽+Tree的Key全部位于葉子節(jié)點(diǎn)，而內(nèi)節(jié)點(diǎn)只用來(lái)索引，所以Cursor在seek()時(shí)，總會(huì)遍歷到葉子節(jié)點(diǎn)。也就是說(shuō)，c.node()總是返回當(dāng)前游標(biāo)指向的葉子節(jié)點(diǎn)的node引用。代碼(6)處通過(guò)c.node()的調(diào)用得到當(dāng)前游標(biāo)處的node后，隨即通過(guò)node的put()方法向node中寫(xiě)入K/V:
//boltdb/bolt/node.go
// put inserts a key/value.
func (n *node) put(oldKey, newKey, value []byte, pgid pgid, flags uint32) {
......
// Find insertion index.
index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, oldKey) != -1 })
// Add capacity and shift nodes if we don't have an exact match and need to insert.
exact := (len(n.inodes) > 0 && index < len(n.inodes) && bytes.Equal(n.inodes[index].key, oldKey))
if !exact {
n.inodes = append(n.inodes, inode{})
copy(n.inodes[index+1:], n.inodes[index:])
}
inode := &n.inodes[index]
inode.flags = flags
inode.key = newKey
inode.value = value
inode.pgid = pgid
_assert(len(inode.key) > 0, "put: zero-length inode key")
}
在node的put()方法中:
- 先查找oldKey以確定插入的位置。要么是正好找到oldKey，則插入位置就是oldKey的位置，實(shí)際上是替換；要么node中不含有oldKey，則插入位置就是第一個(gè)大于oldKey的前一個(gè)key的位置或者是節(jié)點(diǎn)結(jié)尾;
- 如果找到oldKey，則直接用newKey和value替代原來(lái)的oldKey和old value；
- 如果未找到oldKey，則向node中添加一個(gè)inode，并將插入位置后的所有inode向后移一位，以實(shí)現(xiàn)插入新的inode;
到此，我們就了解了整個(gè)Bucket創(chuàng)建的主要過(guò)程：
- 根據(jù)Bucket的名字(key)搜索父Bucket，以確定表示Bucket的K/V對(duì)的插入位置;
- 創(chuàng)建空的內(nèi)置Bucket，并將它序列化成byte slice，以作為Bucket的Value;
- 將表示Bucket的K/V對(duì)(即inode的flags為bucketLeafFlag(0x01))寫(xiě)入父Bucket的葉子節(jié)點(diǎn);
- 通過(guò)Bucket的Bucket(name []byte)在父Bucket中查找剛剛創(chuàng)建的子Bucket，在了解了Bucket通過(guò)Cursor進(jìn)行查找和遍歷的過(guò)程后，讀者可以嘗試自行分析這一過(guò)程，我們?cè)诤罄m(xù)文中還會(huì)介紹Bucket的Get()方法，與此類(lèi)似。
在《區(qū)塊的持久化之BoltDB(一)》中的典型調(diào)用示例中，創(chuàng)建完Bucket后，就可以調(diào)用它的Put()方法向其中添加K/V了:
//boltdb/bolt/node.go
// Put sets the value for a key in the bucket.
// If the key exist then its previous value will be overwritten.
// Supplied value must remain valid for the life of the transaction.
// Returns an error if the bucket was created from a read-only transaction, if the key is blank, if the key is too large, or if the value is too large.
func (b *Bucket) Put(key []byte, value []byte) error {
......
// Move cursor to correct position.
c := b.Cursor()
k, _, flags := c.seek(key)
// Return an error if there is an existing key with a bucket value.
if bytes.Equal(key, k) && (flags&bucketLeafFlag) != 0 {
return ErrIncompatibleValue
}
// Insert into node.
key = cloneBytes(key)
c.node().put(key, key, value, 0, 0)
return nil
}
可以看到，向Bucket添加K/V的過(guò)程與創(chuàng)建Bucket時(shí)的過(guò)程極其相似，因?yàn)閯?chuàng)建Bucket實(shí)際上就是向父Bucket添加一個(gè)標(biāo)識(shí)為Bucket的K/V對(duì)而已。不同的是，這里作了一個(gè)保護(hù)，即當(dāng)欲插入的Key與當(dāng)前Bucket中已有的一個(gè)子Bucket的Key相同時(shí)，會(huì)拒絕寫(xiě)入，從而保護(hù)嵌套的子Bucket的引用不會(huì)被擦除，防止子Bucket變成孤兒。當(dāng)然，我們也可以調(diào)用新創(chuàng)建的子Bucket的CreateBucket()方法來(lái)創(chuàng)建孫Bucket，然后向?qū)OBucket中寫(xiě)入K/V對(duì)，其過(guò)程與我們上述從根Bucket創(chuàng)建子Bucket的過(guò)程是一致的。
到此，我們已經(jīng)介紹了BoltDB中的Tx、Cursor、page、node及Bucket和背后的B+Tree結(jié)構(gòu)等比較核心的概念和機(jī)制，后面我們介紹只讀Transaction中的查找過(guò)程時(shí)將變得非常簡(jiǎn)單。但是，我們提到的B+Tree節(jié)點(diǎn)的分裂和再平衡是什么時(shí)候發(fā)生的呢，它們會(huì)對(duì)B+Tree的結(jié)構(gòu)或者其上的節(jié)點(diǎn)有什么影響呢，新創(chuàng)建的內(nèi)置Bucket什么時(shí)候會(huì)變成一個(gè)普通Bucket呢？這些均是在讀寫(xiě)Transaction Commit的時(shí)候發(fā)生的，我們將在《區(qū)塊的持久化之BoltDB(四)》中介紹。
