page

Page is a specific page representation in the B+ tree. In BoltDB, the default page size is the default page size of the operating system. Page can be divided into different types according to the specific data stored, including: BranchPage (B+ tree non-leaf node), leafPage(B+ tree leaf node), metaPage(store original data page),freeListPage(store current free page ID page);

type page struct {
	id       pgid // The corresponding pageId of the current page
	flags    uint16 // Page Indicates the page type
	count    uint16 // The number of elements stored in the current page
	overflow uint32 // If data cannot be stored in one page at a time, multiple consecutive pages will be allocated to store the data, representing several consecutive pages
	ptr      uintptr // Points to the actual stored data
}
Copy the code

PTR points to different types of pages, and the corresponding page layout is different. The contents and page layout stored in different pages are as follows:

meta page

Pageid =1; pageid=2; pageid=2; for failover? Crash recovery is fast
// Recover database information from the information in these two pages?
// The meta page stores some original data of the current DB, including: magic number, version number, page size, root node
// The page id corresponding to the idle page ID (the page ID corresponding to the idle page id will change), the page ID corresponding to the current page, the maximum transaction ID corresponding to the current page,
// Checksum etc
type meta struct {
	magic    uint32
	version  uint32
	pageSize uint32
	flags    uint32
	root     bucket
	freelist pgid
	pgid     pgid
	txid     txid
	checksum uint64
}
Copy the code

metaPage

branchPage

//branchPageElement represents a node in branchPage
type branchPageElement struct {
	pos   uint32
	ksize uint32 // The length of the current element's key
	pgid  pgid   // The pageId corresponding to element
}
Copy the code

BranchPage consists of the branchPageElement header and a specific key. The page layout is as follows:

branchPage

leafPage

//leafPageElement represents an element in a leaf node
type leafPageElement struct {
	flags uint32 //todo
	pos   uint32 // The offset relative to PTR
	ksize uint32 / / the length of the key
	vsize uint32 / / the length of the value
}
Copy the code

LeafPage consists of leafPageElement header and specific key/value. The specific page layout is as follows:

leafPage