面试问你如何快速优化网站,网站上传到空间,上海地区做旧物回收的网站,网站子页怎么做文章目录 Task1 B树页B树页B树内部结点B树叶子结点 Task2 B树操作Task2 B树插入和搜索的单一值插入单一值搜索单一值 Task2 B树删除 Task3 叶子扫描的迭代器Task4 并行索引 Task1 B树页
B树页
实际上是每个B树页面的标题部分#xff0c;包含叶子页面和内部页面共享的信息。 … 文章目录 Task1 B树页B树页B树内部结点B树叶子结点 Task2 B树操作Task2 B树插入和搜索的单一值插入单一值搜索单一值 Task2 B树删除 Task3 叶子扫描的迭代器Task4 并行索引 Task1 B树页
B树页
实际上是每个B树页面的标题部分包含叶子页面和内部页面共享的信息。
报头格式(大小以字节为单位共12字节):
| PageType (4) | CurrentSize (4) | MaxSize (4) |// define page type enum
enum class IndexPageType { INVALID_INDEX_PAGE 0, LEAF_PAGE, INTERNAL_PAGE };
// 成员变量内部页和叶页共享的属性
IndexPageType page_type_ __attribute__((__unused__));
int size_ __attribute__((__unused__)); // 键值对的数量内部页的第一个键为无效值
int max_size_ __attribute__((__unused__)); // 键值对的容量B树内部结点
在内部页面中存储n个索引键和n1个子指针(page_id)。
指针PAGE_ID(i)指向一个子树其中所有键K满足:K(i) K K(i1)。
注意:由于键的数量不等于子指针的数量所以第一个键总是无效的。也就是说任何搜索/查找都应该忽略第一个键。
内部页面格式(键按递增顺序存储):
| HEADER | KEY(1)PAGE_ID(1) | KEY(2)PAGE_ID(2) | ... | KEY(n)PAGE_ID(n) |#define MappingType std::pairKeyType, ValueType
//key - page_id 的映射
MappingType array_[0];B树叶子结点
只支持唯一键。
叶页格式(键按顺序存储):
| HEADER | KEY(1) RID(1) | KEY(2) RID(2) | ... | KEY(n) RID(n)HEADER格式(大小为字节共16字节):
| PageType (4) | CurrentSize (4) | MaxSize (4) | NextPageId (4)page_id_t next_page_id_; // 先定位到一个叶子再顺序向后扫描
//key-record_id 的映射record id page id combined with slot id
MappingType array_[0];Task2 B树操作
大部分操作在b_plus_tree.cpp实现
Context类用于记录操作B树过程中需要记忆的路径、读写保护等
class Context {public:// 当您插入/删除B树时将头页的写保护存储在这里。// 当您想要解锁所有内容时请记住取消标题页保护并将其设置为空值即header_page.reset()std::optionalWritePageGuard header_page_{std::nullopt};//在这里保存根页面id以便更容易地知道当前页面是否是根页面。page_id_t root_page_id_{INVALID_PAGE_ID};// 要修改的页面的写保护的队列。std::dequeWritePageGuard write_set_;// 读保护队列std::dequeReadPageGuard read_set_;auto IsRootPage(page_id_t page_id) - bool { return page_id root_page_id_; }
};Task2 B树插入和搜索的单一值
插入单一值
BPLUSTREE_TYPE::Insert()实现若BPLUSTREE_TYPE::header_page_id_属性标识的根节点的页BPlusTreeHeaderPage的根节点页id无效说明没有根页面调用缓冲区的NewPage()新建root页然后强转为BPlusTreeLeafPage类型此时根节点就是叶子节点然后BPlusTreeLeafPage::InsertAtLast()根叶后插k-v标识正在使用该页清空header_page_检查header_page_id_标识的根节点页时页就存在这里。若有根节点就获取根节点页id调用InsertIntoLeaf()
BPLUSTREE_TYPE::InsertIntoLeaf()开头就调用了BPLUSTREE_TYPE::FindLeaf()此函数的作用是为插入/删除结点操作寻找目标叶结果存在B树类的Context类成员的write_set_中。回到函数取出查找到的页强转为BPlusTreeLeafPage后直接调用BPlusTreeLeafPage::Insert()插入k-v若插入失败说明是重复键值对清空header_page_和write_set_后退出并且若叶页大小没超过叶子最大容量则此插入是安全插入清空header_page_和write_set_后退出剩下的情况就是叶页满了需要分裂调用Split()进行分裂返回的新页引用是满页分裂出的兄弟叶页之后调用InsertIntoParent()修改父结点结构。
BPLUSTREE_TYPE::InsertIntoParent()是个直接递归在函数开头有个判断write_set_内的锁有一个时这些锁是在InsertIntoLeaf()中调用FindLeaf()时产生的表示修改该叶子会导致write_set_中的这些结点页被修改即最接近叶子的安全结点到叶子节点这一路径上的所有结点的锁。在write_set_中只剩一个页时NewPage()新建一个页当作新根节点然后旧根节点和分裂出的新结点做新根的子节点返回。通过write_set_获取父结点然后调用BPlusTreeInternalPage::InsertAfterValue()将分裂后产生的新节点插入父节点write_set_弹出旧结点原来不安全的结点。当父节点的大小超过了最大容量则父节点不安全调用Split()分裂并调用InsertIntoParent()递归若是安全结点则清理header_page_和write_set_结束。
BPLUSTREE_TYPE::Split()分裂结点返回新的兄弟页。NewPage()创建新页叶子节点分裂就将新页和待分裂的页强转为叶页初始化新叶页后旧叶页调用BPlusTreeLeafPage::SplitLeafTo()取出旧叶页的后一半数据给新叶页并且设置旧叶页和新叶页的next_page_id。最后设置正在使用新叶页然后返回。若分裂内部节点将新页和待分裂的页强转为内部结点页新结点页初始化后旧结点页调用BPlusTreeInternalPage::SplitInternalTo()取内部节点的最大容量加一的一半后半段的内容给新内部节点限定结点大小。设置新结点页正在使用后返回。
这里我不理解的是在InsertIntoParent()中仅仅用if (ctx.write_set_.size() 1)就确定是根节点分裂
搜索单一值
BPLUSTREE_TYPE::GetValue()实现获取头部页的写锁header_page_通过它获得根节点id将根节点读锁加入read_set_然后强转为BPlusTreePage清空header_page_强转结点为BPlusTreeInternalPage调用BPlusTreeInternalPage::FindInternelKey()按key二分查找中间节点的子节点引用查到的页加读锁加入read_set_然后将原先在read_set_中的父页弹出这样就实现了读锁的下沉之后进入循环直到页是叶页。循环出来后将页强转为BPlusTreeLeafPage类之后调用BPlusTreeLeafPage::FindKey()二分查找叶子节点的值找到后组装传参vector。
Task2 B树删除
BPLUSTREE_TYPE::Remove()实现获取头部页写锁并得到根节点id调用FindLeaf()查找key获取查到的页强转成BPlusTreeLeafPage调用BPlusTreeLeafPage::DeleteKey()先二分查找叶子结点key若没有调用DeleteKeyAt()删除数组中对应的k-v删除失败就清理header_page_和write_set_并退出若删除的k-v所在的叶页大小大于等于最小容量叶子结点是max_size_/2内部节点是(max_size_1)/2时即为安全删除清空write_set_并退出若根节点时叶子叶子根节点有一个键值对就能退出。最后都没有退出的就是需要非安全删除情况可能会有修改父节点key、小于最小尺寸需从兄弟节点处拿甚至兄弟节点也不足直接合并调用DealNode()合并或删除叶页。
BPLUSTREE_TYPE::DealNode()是个间接递归它调用Merge()而Merge()调用它。处理借取键值对或合并节点write_set_的最后一个值是这个函数体需要处理的不安全的节点已进行删除工作。 若是根节点 根叶清理write_set_和header_page_不是叶强转为内部节点取第0个的引用做根节点idheader_page_强转为BPlusTreeHeaderPage可取root_page_id_ 返回 不是根 从write_set_取出该页的父页强转为内部节点 是叶 强转为叶页父页调用FindInternelKey()二分查找叶子key获得index 左边有值有左兄弟index 0取左兄弟父页的index-1的写锁存入write_set_强转为叶页后保存变量 右边有值有右兄弟index 父页容量-1取右兄弟父页的index1的写锁存入write_set_强转为叶页后保存变量 左右兄弟都在左叶页变量 右叶页变量 两个兄弟都不足兄弟大小 最小容量调用Merge()与右节点合并返回右边有剩余右兄弟大小 最小容量清空header_page_向兄弟节点借键值对表示父页是安全节点释放write_set_中父页的祖先节点及根的锁叶页调用LendFromBrother()向右兄弟借之后父页调用SetKeyAt()更新父页中的右兄弟结点在父页的索引然后清理write_set_左边有剩余else清空header_page_释放write_set_中父页的祖先节点及根的锁叶页调用LendFromBrother()向左兄弟借父页调用SetKeyAt()更新父页中的右兄弟结点在父页的索引然后清理write_set_ 只有左兄弟左叶页变量 左兄弟不足左兄弟大小 最小容量调用Merge()与左兄弟合并返回左边有剩余清空header_set_释放write_set_中父页祖先节点及根的锁叶页调用LendFromBrother()向左兄弟借父页调用SetKeyAt()更新父页中的左兄弟结点在父页的索引然后清理write_set_ 只有右兄弟右叶页变量 右兄弟不足右兄弟大小 最小容量调用Merge()与右兄弟合并返回右边有剩余清空header_set_释放write_set_中父页祖先节点及根的锁叶页调用LendFromBrother()向右兄弟借父页调用SetKeyAt()更新父页中的右兄弟结点在父页的索引然后清理write_set_ 是内部结点 强转为内部结点页父页调用FindInternelKey()二分查找内部结点获得index 左边有值有左兄弟index 0取左兄弟父页的index-1的写锁存入write_set_强转为内部结点页后保存变量 右边有值有右兄弟index 父页容量-1取右兄弟父页的index1的写锁存入write_set_强转为内部结点后保存变量 左右兄弟都在左结点页变量 右结点页变量 两个兄弟都不足兄弟大小 最小容量调用Merge()与右节点合并返回右边有剩余右兄弟大小 最小容量清空header_page_释放write_set_中父页的祖先节点及根的锁内部结点页调用LendFromBrother()向右兄弟借之后父页调用SetKeyAt()更新父页中的右兄弟结点在父页的索引然后清理write_set_左边有剩余else清空header_page_释放write_set_中父页的祖先节点及根的锁叶页调用LendFromBrother()向左兄弟借父页调用SetKeyAt()更新父页中的右兄弟结点在父页的索引然后清理write_set_ 只有左兄弟左结点页变量 左兄弟不足左兄弟大小 最小容量调用Merge()与左兄弟合并返回左边有剩余清空header_set_释放write_set_中父页祖先节点及根的锁叶页调用LendFromBrother()向左兄弟借父页调用SetKeyAt()更新父页中的左兄弟结点在父页的索引然后清理write_set_ 只有右兄弟右结点页变量 右兄弟不足右兄弟大小 最小容量调用Merge()与右兄弟合并返回右边有剩余清空header_set_释放write_set_中父页祖先节点及根的锁叶页调用LendFromBrother()向右兄弟借父页调用SetKeyAt()更新父页中的右兄弟结点在父页的索引然后清理write_set_
BPLUSTREE_TYPE::Merge()总是把右边节点的键值对转移给左边再删除右边节点这样方便更新NextPageId若传入的经删除操作的页是叶子节点将该页和兄弟页强转为叶页后判断是右兄弟兄弟结点就调用BPlusTreeLeafPage::MoveAllTo()将自己的k-v顺序插入该页的末尾将该页的NextPageId设置为右兄弟的设置删除结点索引为右兄弟索引该页索引1。若判断是左兄弟该页调用BPlusTreeLeafPage::MoveAllTo()将自己的k-v顺序插入左兄弟的尾部左兄弟的NextPageId设置为该页的设置删除节点索引为该页索引。若进行删除操作的页是内部结点强转该页和兄弟页为内部节点页判断是右兄弟就把兄弟k-v插入该页末尾设置删除索引为兄弟反之同理。之后将write_set_中该页父页的孩子出栈解锁只剩父页和其祖先节点把父页强转为内部节点页调用DeleteKeyAt()将删除结点索引指定的结点页删除。若父页大小大于等于最小容量安全删除清理write_set_后就可返回若是根结点内部根节点右两个键值对容量大于1就行返回其他情况就是不安全删除调用DealNode()进行间接递归。
BPlusTreeLeafPage::LendFromBrother()从brother移动一个键值对过来兄弟调用KeyAt()和ValueAt()针对传入是否是左兄弟将k-v插入结点的头或尾并设置兄弟的大小或删除k-v最后返回新key。
Task3 叶子扫描的迭代器 必须添加一个c迭代器以有效地支持对叶页中的数据进行有序扫描。基本思想是存储兄弟指针这样就可以有效地遍历叶页然后实现一个迭代器按顺序遍历每个叶页中的每个键值对。 Begin()和End()函数在b_plus_true.cpp中而迭代器类在index_iterator.cpp中实现
//索引迭代器类的私有属性
BPlusTreeLeafPageKeyType, ValueType, KeyComparator *leaf_page_{nullptr}; // 此迭代器指向的叶子
int index_{-1}; // 表示此迭代器现在指向leaf_page_中某叶页的第几个键值对
page_id_t my_page_id_;//表示迭代器指向的leaf_page_中某叶页的页id
BufferPoolManager *bpm_{nullptr};重载了* !四个符号来对索引迭代器进行操作
BPLUSTREE_TYPE::Begin()有重载分别对应处理没给key和给了key的情况。没给就直接调用FindLeafPage()传入空key并指定找最左边的k-v这样就返回了叶页链表首页然后强转为叶页构造索引迭代器后返回。传入key的Begin()多加了一层检测传回的页是否真的有key没有说明FindLeafPage()没有找到返回空索引迭代器。
BPLUSTREE_TYPE::End()同无参Begin()只不过指定找的是最右边的k-v即indexinternal_page-GetSize()-1
BPLUSTREE_TYPE::FindLeafPage()无锁获取根节点根据传入的indextype判断需要的是最左/右的页还是进行k-v查找。
Task4 并行索引
见Task 2
