SPOJQueryOnATreeIV题解一个边分治套线段树套堆的题目比较难写但是有不小的启发思路来源和代码都抄自[SPOJ-QTREE4]QUERYONATREEIV题解|KSKUN'sBlog简要题意给定一个\(n\)个点的带边权树，点的编号为\(1\simn\)，初始树上所有节点都是白色的，要求维护两个操作：\(\rm{C\a}\)反转\(a\)节点的颜色（白色变成黑色或者黑色变成白色）\(\rmA\)查询树上最远的两个白点的距离特别的，进行\(\rmA\)操作时如果树上没有白点输出Theyhavedisappeared.\(N\le10^5,Q\le10^5,-10^3\lec\le10
SPOJQueryOnATreeIV题解一个边分治套线段树套堆的题目比较难写但是有不小的启发思路来源和代码都抄自[SPOJ-QTREE4]QUERYONATREEIV题解|KSKUN'sBlog简要题意给定一个\(n\)个点的带边权树，点的编号为\(1\simn\)，初始树上所有节点都是白色的，要求维护两个操作：\(\rm{C\a}\)反转\(a\)节点的颜色（白色变成黑色或者黑色变成白色）\(\rmA\)查询树上最远的两个白点的距离特别的，进行\(\rmA\)操作时如果树上没有白点输出Theyhavedisappeared.\(N\le10^5,Q\le10^5,-10^3\lec\le10
实际上它就是B树的变种，以一颗最大度数（max-degree）为4（4阶）的b+tree为例：所有的元素都会出现在叶子节点，叶子节点形成一个单向链表，每一个节点都会通过一个指针指向下一个元素。Mysql索引数据结构对经典的B+Tree树结构进行了优化。在原B+Tree树的基础上，增加了一个指向相邻叶子节点的链表指针，就形成了一个带有顺序指针的B+Tree，提高区间的访问性能。有利于数据库的排序操作。每个数据节点都是存储在一个页当中的。可以通过一个数据结构可视化的网站来简单演示一下。https://www.cs.usfca.edu/~galles/visualization/BPlusTree.
实际上它就是B树的变种，以一颗最大度数（max-degree）为4（4阶）的b+tree为例：所有的元素都会出现在叶子节点，叶子节点形成一个单向链表，每一个节点都会通过一个指针指向下一个元素。Mysql索引数据结构对经典的B+Tree树结构进行了优化。在原B+Tree树的基础上，增加了一个指向相邻叶子节点的链表指针，就形成了一个带有顺序指针的B+Tree，提高区间的访问性能。有利于数据库的排序操作。每个数据节点都是存储在一个页当中的。可以通过一个数据结构可视化的网站来简单演示一下。https://www.cs.usfca.edu/~galles/visualization/BPlusTree.
论文翻译，用于个人学习和记录，英文和专业水平不足，很多地方翻译不出来或者翻译错了，如果有人看到了，希望不吝赐教源文件是从该网址下载的https://dl.acm.org或者链接：https://pan.baidu.com/s/1j2NjTulfHLVu5dvdWKYomA?pwd=p4ka提取码：p4ka如果要看我的翻译的话，建议和英文原版一起看，避免无法理解我的拙劣翻译原文的引用标注了但是没有给出，建议下载英文原版查看有些语句和单词能力不足，或无法理解其在软件工程上存在的特殊意义可能会不翻译或者翻译错误，还是建议和英文原版一起看！（最好就直接啃英文不用看我这个了）TheModularStru
论文翻译，用于个人学习和记录，英文和专业水平不足，很多地方翻译不出来或者翻译错了，如果有人看到了，希望不吝赐教源文件是从该网址下载的https://dl.acm.org或者链接：https://pan.baidu.com/s/1j2NjTulfHLVu5dvdWKYomA?pwd=p4ka提取码：p4ka如果要看我的翻译的话，建议和英文原版一起看，避免无法理解我的拙劣翻译原文的引用标注了但是没有给出，建议下载英文原版查看有些语句和单词能力不足，或无法理解其在软件工程上存在的特殊意义可能会不翻译或者翻译错误，还是建议和英文原版一起看！（最好就直接啃英文不用看我这个了）TheModularStru
B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（Binary），因为B+树是从最早的平衡二叉树演化而来的。二叉查找树二叉树性质：左子树的键值小于根的键值，右子树的键值大于根的键值二叉树搜索相当于一个二分查找，时间复杂度可以达到O(log2(n))二叉树以第一个插入的数据作为根节点，在数据基本有序的情况下，二叉树的构建基本上就是一个线性链表结构。查找最后一个数据等于遍历整个链表，查询效率很低，不稳定。平衡二叉树（AVLTree）平衡二叉树（AVL树）是一颗空树或它的左右两个子树的高度差的绝对值不能超过1，并且
B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（Binary），因为B+树是从最早的平衡二叉树演化而来的。二叉查找树二叉树性质：左子树的键值小于根的键值，右子树的键值大于根的键值二叉树搜索相当于一个二分查找，时间复杂度可以达到O(log2(n))二叉树以第一个插入的数据作为根节点，在数据基本有序的情况下，二叉树的构建基本上就是一个线性链表结构。查找最后一个数据等于遍历整个链表，查询效率很低，不稳定。平衡二叉树（AVLTree）平衡二叉树（AVL树）是一颗空树或它的左右两个子树的高度差的绝对值不能超过1，并且
数据库中非常常用的索引数据结构——B+树，在过去很多年里它都是数据库索引的首选实现方式，但是这种数据结构也并不是很完美。因为，每次修改数据都很有可能破坏B+树的约束，我们需要对整棵树进行递归的合并、分裂等调整操作，而不同节点在磁盘上的位置很可能并不是连续的，这就导致我们需要不断地做随机写入的操作，而随机写入的性能是比较差的，这个问题在写多读少的场景下会更加明显。LSMTree（LogStructureMergeTree）是比B+树更适合写多读少场景的索引结构，也广泛应用在各大NoSQL中。比如基于LSM树实现底层索引结构的RocksDB、LevelDB。LSMTree的实现原理：LSM树包含了
数据库中非常常用的索引数据结构——B+树，在过去很多年里它都是数据库索引的首选实现方式，但是这种数据结构也并不是很完美。因为，每次修改数据都很有可能破坏B+树的约束，我们需要对整棵树进行递归的合并、分裂等调整操作，而不同节点在磁盘上的位置很可能并不是连续的，这就导致我们需要不断地做随机写入的操作，而随机写入的性能是比较差的，这个问题在写多读少的场景下会更加明显。LSMTree（LogStructureMergeTree）是比B+树更适合写多读少场景的索引结构，也广泛应用在各大NoSQL中。比如基于LSM树实现底层索引结构的RocksDB、LevelDB。LSMTree的实现原理：LSM树包含了
