{"repo":"zhjwpku/paper-notes","free":true,"listed":false,"github":"https://github.com/zhjwpku/paper-notes","clone":"git clone https://github.com/zhjwpku/paper-notes.git","description":"📄 📃 papers that I read and noted 🧐","language":null,"stars":39,"topics":["database","distributed-systems","paper","paper-notes"],"license":"WTFPL","category":"databases-storage","readme_excerpt":"论文笔记 I have changed this repo to a mdBook, run mdbook serve to read the notes locally or just visit paper-notes.zhjwpku.com. 目录(TOC) - 论文笔记 - 目录(TOC) - 数据结构(Data Structure) - BTree - The Ubiquitous B-Tree - LSMTree - The Log-Structured Merge-Tree - 分布式(Distributed Systems) - 存储(Storage) - Bigtable: A Distributed Storage System for Structured Data - Persistent Memory - System Evaluation of the Intel Optane Byte-addressable NVM - An Empirical Guide to the Behavior and Use of Scalable Persistent Memory 数据结构(Data Structure) BTree The Ubiquitous B-Tree Unfortunately, a B-tree may not do well in a sequential processing environment. While a simple preorder tree walk [KNUT68] extracts all the keys in order, it requires space for at least h = logd(n + 1) nodes in main memory since it stacks the nodes along a path from the root to avoid reading them twice. Additionally, processing a next operation may require tracing a path through several nodes before reaching the desired key. B\\ Tree B tree 在插入的时候会产生 overflow，可以通过 redistribution 来减少分裂的次数，但真正分离的时候采取的是一分为二的做法，因此只能保证 1/2 的空间利用率。B Tree 同样是通过 redistribution 来减少分离次数，更进一步，只在两个邻居节点都满的时候讲两个节点分离成三个节点，从而使得每个节点达到 2/3 full，降低了树的总高，进而优化检索速度。 但实际中可能应用的并不多。 B+ Tree B+ Tree 在保持树平衡的同时，其所有叶子节点通过指针串联在一起(left-to-right)，因此在顺序遍历下一个 key 的时候，最多只需要一次读盘，而且内存中只需要驻留一个 node。所有串联起来的叶子节点被称为 sequence set 。 B+ Tree 的索引节点和叶子节点通常使用不同的排布格式，因为索引节点不需要 value 信息。 非页节点中的 key 作为 index ，包含了部分 key。B+ Tree 的插入删除操作可在 B+ Tree Visualization 进行实际操作。 另外值得注意的是，在删除数据的时候，可以在 index 中保留删除","default_branch":null,"files":null,"tree":[],"storefront":"/r/zhjwpku","claimed":false,"request_supported":{"post":"https://gitbuyer.com/r/zhjwpku/paper-notes/request-supported","requests":0},"note":"indexed from public GitHub; nothing is for sale on this page. Clone it from GitHub. Paid listings live at /search."}