B+树的实现更多...

#include <bplus_tree.h>

Public 成员函数
RC	create (LogHandler &log_handler, BufferPoolManager &bpm, const char *file_name, AttrType attr_type, int attr_length, int internal_max_size=-1, int leaf_max_size=-1)
	创建一个B+树更多...

RC	create (LogHandler &log_handler, DiskBufferPool &buffer_pool, AttrType attr_type, int attr_length, int internal_max_size=-1, int leaf_max_size=-1)

RC	open (LogHandler &log_handler, BufferPoolManager &bpm, const char *file_name)
	打开一个B+树更多...

RC	open (LogHandler &log_handler, DiskBufferPool &buffer_pool)

RC	close ()

RC	insert_entry (const char user_key, const RID rid)
	此函数向IndexHandle对应的索引中插入一个索引项。更多...

RC	delete_entry (const char user_key, const RID rid)
	从IndexHandle句柄对应的索引中删除一个值为（user_key，rid）的索引项更多...

bool	is_empty () const

RC	get_entry (const char *user_key, int key_len, list< RID > &rids)
	获取指定值的record 更多...

RC	sync ()

bool	validate_tree ()

const IndexFileHeader &	file_header () const

DiskBufferPool &	buffer_pool () const

LogHandler &	log_handler () const

RC	recover_update_root_page (BplusTreeMiniTransaction &mtr, PageNum root_page_num)
	恢复更新ROOT页面更多...

RC	recover_init_header_page (BplusTreeMiniTransaction &mtr, Frame *frame, const IndexFileHeader &header)
	恢复初始化头页面更多...

RC	print_tree ()

RC	print_leafs ()

Protected 成员函数
RC	find_leaf (BplusTreeMiniTransaction &mtr, BplusTreeOperationType op, const char key, Frame &frame)
	查找叶子节点更多...

RC	left_most_page (BplusTreeMiniTransaction &mtr, Frame *&frame)
	找到最左边的叶子节点

RC	find_leaf_internal (BplusTreeMiniTransaction &mtr, BplusTreeOperationType op, const function< PageNum(InternalIndexNodeHandler &)> &child_page_getter, Frame *&frame)
	查找指定的叶子节点更多...

RC	crabing_protocal_fetch_page (BplusTreeMiniTransaction &mtr, BplusTreeOperationType op, PageNum page_num, bool is_root_page, Frame *&frame)
	使用crabing protocol 获取页面

RC	delete_entry_internal (BplusTreeMiniTransaction &mtr, Frame leaf_frame, const char key)
	从叶子节点中删除指定的键值对

template<typename IndexNodeHandlerType >
RC	split (BplusTreeMiniTransaction &mtr, Frame frame, Frame &new_frame)
	拆分节点更多...

template<typename IndexNodeHandlerType >
RC	coalesce_or_redistribute (BplusTreeMiniTransaction &mtr, Frame *frame)
	合并或重新分配更多...

template<typename IndexNodeHandlerType >
RC	coalesce (BplusTreeMiniTransaction &mtr, Frame neighbor_frame, Frame frame, Frame *parent_frame, int index)
	合并两个相邻节点更多...

template<typename IndexNodeHandlerType >
RC	redistribute (BplusTreeMiniTransaction &mtr, Frame neighbor_frame, Frame frame, Frame *parent_frame, int index)
	重新分配两个相邻节点更多...

RC	insert_entry_into_parent (BplusTreeMiniTransaction &mtr, Frame frame, Frame new_frame, const char *key)
	在父节点插入一个元素更多...

RC	insert_entry_into_leaf_node (BplusTreeMiniTransaction &mtr, Frame frame, const char pkey, const RID *rid)
	在叶子节点插入一个元素

RC	create_new_tree (BplusTreeMiniTransaction &mtr, const char key, const RID rid)
	创建一个新的B+树

void	update_root_page_num_locked (BplusTreeMiniTransaction &mtr, PageNum root_page_num)
	更新根节点的页号

RC	adjust_root (BplusTreeMiniTransaction &mtr, Frame *root_frame)
	调整根节点

Protected 属性
LogHandler *	log_handler_ = nullptr

DiskBufferPool *	disk_buffer_pool_ = nullptr
	日志处理器

bool	header_dirty_ = false
	磁盘缓冲池

IndexFileHeader	file_header_
	是否需要更新头页面

common::SharedMutex	root_lock_

KeyComparator	key_comparator_

KeyPrinter	key_printer_

unique_ptr< common::MemPoolItem >	mem_pool_item_

Private 成员函数
RC	print_leaf (Frame *frame)

RC	print_internal_node_recursive (Frame *frame)

bool	validate_leaf_link (BplusTreeMiniTransaction &mtr)

bool	validate_node_recursive (BplusTreeMiniTransaction &mtr, Frame *frame)

common::MemPoolItem::item_unique_ptr	make_key (const char *user_key, const RID &rid)

友元
class	BplusTreeScanner

class	BplusTreeTester

详细描述

B+树的实现

成员函数说明

◆ close()

RC BplusTreeHandler::close ( )

关闭句柄indexHandle对应的索引文件

◆ coalesce()

template<typename IndexNodeHandlerType >

RC BplusTreeHandler::coalesce	(	BplusTreeMiniTransaction &	mtr,
		Frame *	neighbor_frame,
		Frame *	frame,
		Frame *	parent_frame,
		int	index
	)

protected

合并两个相邻节点

合并两个节点

当节点中的键值对小于最小值并且相邻两个节点总和不超过最大节点个数时，需要合并两个相邻节点

当某个节点数据量太少时，并且它跟它的邻居加在一起都不超过最大值，就需要跟它旁边的节点做合并。可能是内部节点，也可能是叶子节点。叶子节点还需要维护next_page指针。

模板参数

IndexNodeHandlerType 模板类，可能是内部节点，也可能是叶子节点

参数

mtr	mini transaction
neighbor_frame	要合并的邻居页面
frame	即将合并的页面
parent_frame	父节点页面
index	在父节点的哪个位置

◆ coalesce_or_redistribute()

template<typename IndexNodeHandlerType >

RC BplusTreeHandler::coalesce_or_redistribute	(	BplusTreeMiniTransaction &	mtr,
		Frame *	frame
	)

protected

合并或重新分配

当节点中的键值对小于最小值时，需要合并或重新分配

◆ create()

RC BplusTreeHandler::create	(	LogHandler &	log_handler,
		BufferPoolManager &	bpm,
		const char *	file_name,
		AttrType	attr_type,
		int	attr_length,
		int	internal_max_size = `-1`,
		int	leaf_max_size = `-1`
	)

创建一个B+树

参数

log_handler	记录日志
bpm	缓冲池管理器
file_name	文件名
attr_type	属性类型
attr_length	属性长度
internal_max_size	内部节点最大大小
leaf_max_size	叶子节点最大大小

◆ delete_entry()

RC BplusTreeHandler::delete_entry	(	const char *	user_key,
		const RID *	rid
	)

从IndexHandle句柄对应的索引中删除一个值为（user_key，rid）的索引项

返回: RECORD_INVALID_KEY 指定值不存在

注解: 这里假设user_key的内存大小与attr_length 一致

◆ find_leaf()

RC BplusTreeHandler::find_leaf	(	BplusTreeMiniTransaction &	mtr,
		BplusTreeOperationType	op,
		const char *	key,
		Frame *&	frame
	)

protected

查找叶子节点

参数

	op	当前想要执行的操作。操作类型不同会在查找的过程中加不同类型的锁
	key	查找的键值
[out]	frame	返回找到的叶子节点

◆ find_leaf_internal()

RC BplusTreeHandler::find_leaf_internal	(	BplusTreeMiniTransaction &	mtr,
		BplusTreeOperationType	op,
		const function< PageNum(InternalIndexNodeHandler &)> &	child_page_getter,
		Frame *&	frame
	)

protected

查找指定的叶子节点

参数

	op	当前想要执行的操作。操作类型不同会在查找的过程中加不同类型的锁
	child_page_getter	用于获取子节点的函数
[out]	frame	返回找到的叶子节点

◆ get_entry()

RC BplusTreeHandler::get_entry	(	const char *	user_key,
		int	key_len,
		list< RID > &	rids
	)

获取指定值的record

参数

key_len	user_key的长度
rid	返回值，记录记录所在的页面号和slot

◆ insert_entry()

RC BplusTreeHandler::insert_entry	(	const char *	user_key,
		const RID *	rid
	)

此函数向IndexHandle对应的索引中插入一个索引项。

参数user_key指向要插入的属性值，参数rid标识该索引项对应的元组，即向索引中插入一个值为（user_key，rid）的键值对

注解: 这里假设user_key的内存大小与attr_length 一致

◆ insert_entry_into_parent()

RC BplusTreeHandler::insert_entry_into_parent	(	BplusTreeMiniTransaction &	mtr,
		Frame *	frame,
		Frame *	new_frame,
		const char *	key
	)

protected

在父节点插入一个元素

当前这个父节点还没有满，直接将新节点数据插进入就行了

◆ open()

RC BplusTreeHandler::open	(	LogHandler &	log_handler,
		BufferPoolManager &	bpm,
		const char *	file_name
	)

打开一个B+树

参数

log_handler	记录日志
bpm	缓冲池管理器
file_name	文件名

◆ print_leaf()

RC BplusTreeHandler::print_leaf ( Frame * frame )

private

这些函数都是线程不安全的，不要在多线程的环境下调用

◆ print_tree()

RC BplusTreeHandler::print_tree ( )

这些函数都是线程不安全的，不要在多线程的环境下调用

◆ recover_init_header_page()

RC BplusTreeHandler::recover_init_header_page	(	BplusTreeMiniTransaction &	mtr,
		Frame *	frame,
		const IndexFileHeader &	header
	)

恢复初始化头页面

重做日志时调用的接口

◆ recover_update_root_page()

RC BplusTreeHandler::recover_update_root_page	(	BplusTreeMiniTransaction &	mtr,
		PageNum	root_page_num
	)

恢复更新ROOT页面

重做日志时调用的接口

◆ redistribute()

template<typename IndexNodeHandlerType >

RC BplusTreeHandler::redistribute	(	BplusTreeMiniTransaction &	mtr,
		Frame *	neighbor_frame,
		Frame *	frame,
		Frame *	parent_frame,
		int	index
	)

protected

重新分配两个相邻节点

删除某个元素后，对应节点的元素个数比较少，并且与相邻节点不能合并，就将邻居节点的元素移动一些过来

◆ split()

template<typename IndexNodeHandlerType >

RC BplusTreeHandler::split	(	BplusTreeMiniTransaction &	mtr,
		Frame *	frame,
		Frame *&	new_frame
	)

protected

拆分节点

当节点中的键值对超过最大值时，需要拆分节点

split one full node into two

◆ validate_tree()

bool BplusTreeHandler::validate_tree ( )

Check whether current B+ tree is invalid or not.

返回: true means current tree is valid, return false means current tree is invalid.

注解: thread unsafe

该类的文档由以下文件生成:

src/observer/storage/index/bplus_tree.h
src/observer/storage/index/bplus_tree.cpp

Public 成员函数

Protected 成员函数

Protected 属性

Private 成员函数

友元

详细描述

成员函数说明

◆ close()

◆ coalesce()

◆ coalesce_or_redistribute()

◆ create()

◆ delete_entry()

◆ find_leaf()

◆ find_leaf_internal()

◆ get_entry()

◆ insert_entry()

◆ insert_entry_into_parent()

◆ open()

◆ print_leaf()

◆ print_tree()

◆ recover_init_header_page()

◆ recover_update_root_page()

◆ redistribute()

◆ split()

◆ validate_tree()