B+树的实现更多...

#include <bplus_tree.h>

Public 成员函数
RC	create (const char *file_name, AttrType attr_type, int attr_length, int internal_max_size=-1, int leaf_max_size=-1)

RC	open (const char *file_name)

RC	close ()

RC	insert_entry (const char user_key, const RID rid)

RC	delete_entry (const char user_key, const RID rid)

bool	is_empty () const

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

RC	sync ()

bool	validate_tree ()

RC	print_tree ()

RC	print_leafs ()

Protected 成员函数
RC	find_leaf (LatchMemo &latch_memo, BplusTreeOperationType op, const char key, Frame &frame)

RC	left_most_page (LatchMemo &latch_memo, Frame *&frame)

RC	find_leaf_internal (LatchMemo &latch_memo, BplusTreeOperationType op, const std::function< PageNum(InternalIndexNodeHandler &)> &child_page_getter, Frame *&frame)

RC	crabing_protocal_fetch_page (LatchMemo &latch_memo, BplusTreeOperationType op, PageNum page_num, bool is_root_page, Frame *&frame)

RC	insert_into_parent (LatchMemo &latch_memo, PageNum parent_page, Frame left_frame, const char pkey, Frame &right_frame)

RC	delete_entry_internal (LatchMemo &latch_memo, Frame leaf_frame, const char key)

template<typename IndexNodeHandlerType >
RC	split (LatchMemo &latch_memo, Frame frame, Frame &new_frame)

template<typename IndexNodeHandlerType >
RC	coalesce_or_redistribute (LatchMemo &latch_memo, Frame *frame)

template<typename IndexNodeHandlerType >
RC	coalesce (LatchMemo &latch_memo, Frame neighbor_frame, Frame frame, Frame *parent_frame, int index)

template<typename IndexNodeHandlerType >
RC	redistribute (Frame neighbor_frame, Frame frame, Frame *parent_frame, int index)

RC	insert_entry_into_parent (LatchMemo &latch_memo, Frame frame, Frame new_frame, const char *key)

RC	insert_entry_into_leaf_node (LatchMemo &latch_memo, Frame frame, const char pkey, const RID *rid)

RC	create_new_tree (const char key, const RID rid)

void	update_root_page_num (PageNum root_page_num)

void	update_root_page_num_locked (PageNum root_page_num)

RC	adjust_root (LatchMemo &latch_memo, Frame *root_frame)

Protected 属性
DiskBufferPool *	disk_buffer_pool_ = nullptr

bool	header_dirty_ = false

IndexFileHeader	file_header_

common::SharedMutex	root_lock_

KeyComparator	key_comparator_

KeyPrinter	key_printer_

std::unique_ptr< common::MemPoolItem >	mem_pool_item_

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

RC	print_internal_node_recursive (Frame *frame)

bool	validate_leaf_link (LatchMemo &latch_memo)

bool	validate_node_recursive (LatchMemo &latch_memo, Frame *frame)

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

void	free_key (char *key)

友元
class	BplusTreeScanner

class	BplusTreeTester

详细描述

B+树的实现

成员函数说明

◆ close()

RC BplusTreeHandler::close ( )

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

◆ create()

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

此函数创建一个名为fileName的索引。 attrType描述被索引属性的类型，attrLength描述被索引属性的长度

◆ delete_entry()

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

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

返回: RECORD_INVALID_KEY 指定值不存在

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

◆ get_entry()

RC BplusTreeHandler::get_entry	(	const char *	user_key,
		int	key_len,
		std::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	(	LatchMemo &	latch_memo,
		Frame *	frame,
		Frame *	new_frame,
		const char *	key
	)

protected

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

◆ open()

RC BplusTreeHandler::open ( const char * file_name )

打开名为fileName的索引文件。如果方法调用成功，则indexHandle为指向被打开的索引句柄的指针。索引句柄用于在索引中插入或删除索引项，也可用于索引的扫描

◆ print_leaf()

RC BplusTreeHandler::print_leaf ( Frame * frame )

private

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

◆ print_tree()

RC BplusTreeHandler::print_tree ( )

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

◆ split()

template<typename IndexNodeHandlerType >

RC BplusTreeHandler::split	(	LatchMemo &	latch_memo,
		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 成员函数

友元