我的想法是:在大多数数据库中使用的B+树中,非叶节点是指向其他节点的指针集合。每个集合(节点)都是一个有序列表。叶节点,即所有数据指针所在的节点,是一个数据指针群的链表。
非叶节点只是用来找到正确的叶节点,从而找到目标数据指针所在的位置。因此,由于叶节点就像一个链表,为什么不直接去掉树元素,只保留链表呢?可以提供元数据,给出每个叶节点群的最小值和最大值,这样应用程序就可以读取元数据并找到正确的叶子,从而找到数据指针所在的位置。
需要明确的是,对于随机访问的有序列表,最有效的搜索算法是二分查找,其性能为O(log n),与B树相同。使用链表而不是树的好处是它们不需要平衡。
这种结构可行吗?