其他系列文章导航
文章目录
前言
Blink 树和 B+ 树都是一种类似于B树的数据结构，用于在磁盘上存储和索引数据以实现高效查找和操作。它们的主要区别在于内部节点和叶子节点的结构以及指针的使用方式。
一、B+ tree
1.1 B+ tree 定义
B+ 树则是将内部节点和叶子节点分开存储的，内部节点只存储索引键，而叶子节点则存储数据指针。叶子节点之间通过指针连接，形成一个有序链表，这样可以加速范围查询和顺序遍历操作。
1.2 B+ tree 原理
主要是并发场景下，写操作导致节点分裂（SMO，Split Merge Operation）的时候，刚好有并发读操作访问到错误的叶子节点，查错了节点，那么目标值肯定就搜索不到了，于是导致了错误查询。
举个例子：
编辑
此时，插入一个数据 27，恰好页A满了，需要触发分裂，新增一个页B，且同时有个读取请求，想要访问数据 29。
编辑
那么很有可能在分裂的时候，读请求访问到老的页面指针，指向了页 A，而页 A 内的 29 已经被分裂到新的页 B 中，这样一来读请求就发现没有 29 ，于是返回没数据，这就错乱了。
而且，叶子节点的分裂，可能会导致父节点的分裂，这种调整最长可能级联到根节点，并发场景下很容易导致错误，为了避免这种情况的发生，最简单的操作就是在发生节点分裂时，把整颗 B+ Tree 都锁了。
这样一来数据的正确性得到了保证，但是性能就很低了，因为全局锁会影响了对所有页的访问。
后续 MySQL 对其在 5.7 版本后做了优化，但是整个 B+Tree 同时只能支持一个 SMO 操作的发生，高并发时大数据量插入导致多 SMO 的发生还是会被阻塞，影响性能。
二、Blink Tree
2.1 Blink Tree 定义
Blink 树是一种新型的数据结构，它将内部节点和叶子节点合并为一个节点，因此在 Blink 树中不存在内部节点和叶子节点的概念。每个节点中存储了索引键和数据指针，这样可以减少内部节点的数量，降低树的高度，从而提高查询性能。
2.2 Blink tree 原理
Blink Tree 主要引入了 high key 和 link 指针来解决并发读写中间态数据访问出错问题，能降低锁的粒度，提高性能。
high key 存储了每个节点的最大值，每个节点的 link 指针则指向了同层右侧的兄弟节点，在写入数据的时候，仅需对当前节点加锁，当前节点修改完毕后立马解锁，锁的粒度很细，并发度很高。
直接来看来阿里云官网给的一个示意图：
编辑
可以看到，相比于 B+ Tree，Blink Tree 的兄弟节点也进行了指针相连，当分裂在进行中还未完成，也就是父节点到新的子节点的链接还没有建立时，B+ Tree 我们已经演示过了，并发读可能导致数据查询不到。
而 Blink Tree 就能解决这个问题，当读请求沿着老指针访问老页面的时候，对比下 high key，发现查询的值比当前页 high key 大，那么就沿着 link 指针找到旁边新分配的页面，此时就可以找到要查询的值了。
三、总结
总的来说，Blink 树的特点是将内部节点和叶子节点合并为一个节点，减少了树的高度；而 B+ 树通过叶子节点之间的有序链表提高了范围查询和顺序遍历的性能。
Blink tree 真的牛啊！
最后附上简单 B+ tree 的 Python 实现：
class Node: def __init__(self, is_leaf=False): self.is_leaf = is_leaf self.keys = [] self.children = [] class BPlusTree: def __init__(self, degree): self.root = Node(is_leaf=True) self.degree = degree def insert(self, key, value): if key in self.root.keys: # 如果键已经存在，更新值 index = self.root.keys.index(key) self.root.children[index+1] = value else: if len(self.root.keys) == (2*self.degree - 1): # 如果根节点已满，进行分裂 new_root = Node() new_root.children.append(self.root) self.split_child(new_root, 0) self._insert_non_full(new_root, key, value) self.root = new_root else: self._insert_non_full(self.root, key, value) def _insert_non_full(self, node, key, value): if node.is_leaf: # 如果是叶子节点，直接插入 index = 0 for i in range(len(node.keys)): if key > node.keys[i]: index += 1 node.keys.insert(index, key) node.children.insert(index+1, value) else: # 如果是内部节点，递归插入到子节点 index = 0 for i in range(len(node.keys)): if key > node.keys[i]: index += 1 if len(node.children[index].keys) == (2*self.degree - 1): self.split_child(node, index) if key > node.keys[index]: index += 1 self._insert_non_full(node.children[index], key, value) def split_child(self, parent, index): child = parent.children[index] new_child = Node(is_leaf=child.is_leaf) parent.keys.insert(index, child.keys[self.degree-1]) parent.children.insert(index+1, new_child) new_child.keys = child.keys[self.degree:] child.keys = child.keys[:self.degree-1] if not child.is_leaf: new_child.children = child.children[self.degree:] child.children = child.children[:self.degree] def search(self, key): return self._search(self.root, key) def _search(self, node, key): index = 0 for i in range(len(node.keys)): if key >= node.keys[i]: index = i if key == node.keys[index]: return node.children[index+1] elif node.is_leaf: return None else: return self._search(node.children[index], key)
