正文 

当前位置： 首页 > 问答 >

如何在 Haskell 中实现 B+ 树？

     2023-03-11     86

关键词：

【中文标题】如何在 Haskell 中实现 B+ 树？【英文标题】：How to implement B+ tree in Haskell? 【发布时间】：2013-12-17 01:14:23 【问题描述】：

B+ 树的叶节点链接在一起。将 B+ 树的指针结构视为有向图，它不是循环的。但是忽略指针的方向并将其视为无向的叶节点链接在一起会在图中创建循环。

在 Haskell 中，如何将叶子构造为父内部节点的子节点，同时又是来自相邻叶子节点的下一个链接。用 Haskell 的代数数据类型怎么能做到这一点？似乎 Haskell ADT 通常使类似循环的结构难以表达。

【问题讨论】：

假设您想要可变的 B+ 树，对于“链接”，您将使用 IORef/MVar/TVar/etc 来构建“链接”。然后这个过程看起来就像其他语言一样。 Matthew Brecknell 制作了一个视频，解释了使用 GADT 创建 B 树的过程，您可以在 matthew.brecknell.net/post/btree-gadt 上查看。这不是您想要的，但应该是一个很好的起点。 【参考方案1】：

也许这与您正在寻找的相似？

data Node key value
    = Empty
    | Internal key [Node key value] -- key and children
    | Leaf value (Node key value) -- value and next-leaf
    deriving Show

let a = Leaf 0 b
    b = Leaf 1 c
    c = Leaf 2 d
    d = Leaf 3 Empty
in  Internal [Internal 0 [a,b], Internal 2 [c,d]]

这个定义的一个问题是它不会阻止Leaf 节点中的下一个叶子成为Internal 节点。

用 Haskell 制作循环结构实际上很容易，甚至是无限的。例如，下面是一个无限的零列表，它是循环的。

let a = 0:a

您甚至可以进行相互递归，这更加循环：

let a = 0:b
    b = 1:a
in  a

【讨论】：

顺便说一下，这是多路树，而不是 B+ 树。此外，这并不妨碍我们将任何无效值放入 Leaf 构造函数的 next-leaf 参数中。【参考方案2】：

以下是（不可变/“可变”通过重构/zipperable）ADT 表示（涉及不可变vectors）的想法：

module Data.BTree.Internal where

import Data.Vector

type Values v = Vector v

type Keys k = Vector k

data Leaf k v
  = Leaf
     _leafKeys   :: !(Keys k)
    , _leafValues :: !(Values v)
    , _leafNext   :: !(Maybe (Leaf k v)) -- @Maybe@ is lazy in @Just@, so this strict mark
                                         -- is ok for tying-the-knot stuff.
    -- , _leafPrev   :: !(Maybe (Leaf k v))
    -- ^ for doubly-linked lists of leaves
    

type Childs k v = Vector (BTree k v)

data Node k v
  = Node
     _nodeKeys   :: !(Keys k)
    , _nodeChilds :: !(Childs k v)
    

data BTree k v
  = BTreeNode !(Node k v)
  | BTreeLeaf !(Leaf k v)

newtype BTreeRoot k v
  = BTreeRoot (BTree k v)

这应该是内部的，因此不当使用原始构造函数、访问器或模式匹配不会破坏树。

可以添加Keys、Values、Childs 长度控制（使用运行时检查或可能使用 GADT 等）。

对于接口：

module Data.BTree ( - appropriate exports - ) where

import Data.Vector
import Data.BTree.Internal

-- * Building trees: "good" constructors.

keys :: [k] -> Keys k
keys = fromList

values :: [v] -> Values v
values = fromList

leaves :: [Leaf k v] -> Childs k v
leaves = fromList . fmap BTreeLeaf

leaf :: Keys k -> Values v -> Maybe (Leaf k v) -> Leaf k v
-- or
-- leaf :: Keys k -> Values v -> Maybe (Leaf k v) -> Maybe (Leaf k v) -> Leaf k v
-- for doubly-linked lists of leaves
leaf = Leaf

node :: Keys k -> Childs k v -> BTree k v
node ks = BTreeNode . Node ks

-- ...

-- * "Good" accessors.

-- ...

-- * Basic functions: insert, lookup, etc.

-- ...

那么这种树：

可以构建为

test :: BTree Int ByteString
test = let
  root  = node (keys [3, 5]) (leaves [leaf1, leaf2, leaf3])
  leaf1 = leaf (keys [1, 2]) (values ["d1", "d2"]) (Just leaf2)
  leaf2 = leaf (keys [3, 4]) (values ["d3", "d4"]) (Just leaf3)
  leaf3 = leaf (keys [5, 6, 7]) (values ["d5", "d6", "d7"]) Nothing
  in root

这种技术称为"tying the knot"。叶子可以循环：

  leaf1 = leaf (keys [1, 2]) (values ["d1", "d2"]) (Just leaf2)
  leaf2 = leaf (keys [3, 4]) (values ["d3", "d4"]) (Just leaf3)
  leaf3 = leaf (keys [5, 6, 7]) (values ["d5", "d6", "d7"]) (Just leaf1)

或双重链接（假设_leafPrev和对应的leaf函数）：

  leaf1 = leaf (keys [1, 2]) (values ["d1", "d2"]) (Just leaf2) (Just leaf3)
  leaf2 = leaf (keys [3, 4]) (values ["d3", "d4"]) (Just leaf3) (Just leaf1)
  leaf3 = leaf (keys [5, 6, 7]) (values ["d5", "d6", "d7"]) (Just leaf1) (Just leaf2)

使用mutable vectors 和mutable references 也可以实现完全可变的表示：

type Values v = IOVector v

type Keys k = IOVector k

type Childs k v = IOVector (BTree k v)

    , _leafNext   :: !(IORef (Maybe (Leaf k v)))

等等，基本一样，但是使用IORef和IOVector，工作在IO monad。

【讨论】：

但是不可变的方法可以用于例如插入操作吗？ @user782220 insert 应该是带有签名Ord k => k -> v -> BTreeRoot k v -> BTreeRoot k v 的函数（采用“旧”树并返回“新”），问题是新旧之间可以共享多少数据树（在不可变结构之间共享数据很常见），对于简单的 B 树，可以共享不受影响的子树，但如果叶子是链接的，则应该再次重建整个树。可以通过使链接可变 (!(IORef (Maybe (Leaf k v)))) 来修复它，使向量不可变（或不可变，取决于其他可能的问题（例如重新分配））。 你仍然可以获得一些分享，但会少一些。 @JJJ：Haskell 菜鸟。是否可以将newtype 用于Keys 和Values 而不是type？有什么优点/缺点？

如何在 Haskell 中表示两棵树之间的映射？

】如何在Haskell中表示两棵树之间的映射？【英文标题】：HowtorepresentmappingbetweentwotreesinHaskell?【发布时间】：2019-09-0421:37:05【问题描述】：我正在尝试在Haskell中实现树处理算法，并且（由于这是我的第一个Haskell程序！），我正... 查看详情

在 Haskell 中实现 Smullyan 的算术鸟

】在Haskell中实现Smullyan的算术鸟【英文标题】：ImplementingSmullyan\'sarithmeticalbirdsinHaskell【发布时间】：2014-02-0419:37:55【问题描述】：在搜索RaymondSmullyan的ToMockaMockingbird的信息时，我偶然发现了StephenTetley\'sHaskellcodeforthebasiccombinators... 查看详情

在 IRC 机器人 (Haskell) 中实现 CTCP 命令

】在IRC机器人(Haskell)中实现CTCP命令【英文标题】：ImplementingCTCPcommandsinanIRCbot(Haskell)【发布时间】：2011-01-2409:47:30【问题描述】：我已按照Haskellwiki上关于implementinganIRCbot.的教程进行操作，一切正常。但是一旦我开始扩展它，我... 查看详情

Weka：如何在 J48 决策树中实现代理拆分？

】Weka：如何在J48决策树中实现代理拆分？【英文标题】：Weka:HowcanIimplementaSurrogateSplitinJ48DecisionTree?【发布时间】：2014-08-2901:56:43【问题描述】：任何人都可以帮助我使用Java中的WekaAPI在J48算法中实现替代的缺失值处理。我确信在... 查看详情

如何在 C# 中实现交互式决策树

】如何在C#中实现交互式决策树【英文标题】：HowtoimplementaninteractivedecisiontreeinC#【发布时间】：2020-02-0312:58:31【问题描述】：我需要允许用户通过在屏幕上显示的两个简单选项之间进行选择来选择自己的路径，以便进入下一组选... 查看详情

如何在 MVC 剑道树列表编辑器中实现剑道自动完成下拉菜单

】如何在MVC剑道树列表编辑器中实现剑道自动完成下拉菜单【英文标题】：howtoimplementkendoautocompletedropdowninMVCkendotreelisteditor【发布时间】：2018-08-2912:50:12【问题描述】：ScreenCode在此屏幕中，我们使用了剑道树列表。我需要在CODE... 查看详情

如何在 C 中实现多分支树结构

】如何在C中实现多分支树结构【英文标题】：HowtoimplementamultibranchtreestructureinC【发布时间】：2011-08-2713:14:14【问题描述】：我很久没有用C写代码了。我正在尝试做一棵多叶树。我正在尝试将C#trie实现转换为C，以便使用CUDA在GPU... 查看详情

在具有 O(1) 元素访问的 Haskell 中实现高效的拉链式数据结构

】在具有O(1)元素访问的Haskell中实现高效的拉链式数据结构【英文标题】：ImplementingefficientzipperlikedatastructureinHaskellwithO(1)elementsaccess【发布时间】：2013-11-2503:40:09【问题描述】：问题我想创建一个数据类型，它允许快速访问和修... 查看详情

如何在 JavaScript 中实现锁

】如何在JavaScript中实现锁【英文标题】：HowtoimplementalockinJavaScript【发布时间】：2011-07-1719:55:47【问题描述】：如何在JavaScript中实现与C#中的lock等效的东西？所以，为了解释我的想法，一个简单的用例是：用户点击按钮B。B引发o... 查看详情

如何在 RDB 中实现常规索引和复合索引？

】如何在RDB中实现常规索引和复合索引？【英文标题】：HowareregularandcompositeindexesimplementedinRDBs?【发布时间】：2010-11-1023:46:54【问题描述】：在MySQL或Oracle等数据库中，索引是如何实现的？我认为常规索引存储为B树，但找不到任... 查看详情

B树节点如何表示？

】B树节点如何表示？【英文标题】：HowcanaB-treenodeberepresented?【发布时间】：2012-02-2607:47:02【问题描述】：我们正在课堂上学习B树，并被要求在代码中实现它们。老师把编程语言的选择留给了我们，我想尝试用C#来做。我的问题... 查看详情

如何使用 asp.net Web 表单在 Telerik 树中实现搜索和过滤

】如何使用asp.netWeb表单在Telerik树中实现搜索和过滤【英文标题】：HowtoimplementSearchandfillterinteleriktreeusingasp.netwebform【发布时间】：2022-01-1008:40:28【问题描述】：我是telerik的新手。我想过滤telerik:redtree数据但无法在收件箱中触发... 查看详情

如何在剃须刀页面中实现 Treeview

】如何在剃须刀页面中实现Treeview【英文标题】：howtoimplementTreeviewinrazorpage【发布时间】：2021-10-2700:51:53【问题描述】：previousquest我在razor页面中创建树视图当我尝试在cshtml中同时调用多个树视图时，我最终使用了递归函数。程... 查看详情

如何在 JavaScript 中实现决策树。寻找比我丑陋的解决方案更好的解决方案[关闭]

】如何在JavaScript中实现决策树。寻找比我丑陋的解决方案更好的解决方案[关闭]【英文标题】：Howtoimplementadecisiontreeinjavascript.Lookingforabettersolutionthanmyuglyones[closed]【发布时间】：2012-01-1205:06:08【问题描述】：我正在寻找一种在jav... 查看详情

如何在 Laravel 关系中实现 SUM()？

】如何在Laravel关系中实现SUM()？【英文标题】：HowcanIimplementSUM()inLaravelrelations?【发布时间】：2018-08-0506:54:35【问题描述】：这是我的查询，也可以：SELECTsum(r.rating)asrank,b.*FROMbooksasbLEFTJOINranksasrONb.id=r.book_idWHERE1GROUPBY(b.id)ORDERBYrankD... 查看详情

如何在 Django 中实现广义唯一性 DB 约束 (A,B) 和 (B,A)？

】如何在Django中实现广义唯一性DB约束(A,B)和(B,A)？【英文标题】：HowtoimplementageneralizeduniquenessDBconstraint(A,B)and(B,A)inDjango?【发布时间】：2021-11-1217:36:36【问题描述】：我想在使用字段one=\'a\'和two=\'b\'创建对象之前检查数据库，如... 查看详情

WPF treeview：如何在资源管理器中实现键盘导航？

】WPFtreeview：如何在资源管理器中实现键盘导航？【英文标题】：WPFtreeview:howtoimplementkeyboardnavigationlikeinExplorer?【发布时间】：2011-04-1608:23:49【问题描述】：我是第一次使用WPF树视图，我对它所做的所有基本操作感到惊讶不。其... 查看详情

我想在表 A 中提取一些在表 B 中没有条目的列。如何在 Hive 中实现这一点？

】我想在表A中提取一些在表B中没有条目的列。如何在Hive中实现这一点？【英文标题】：IwanttoextractsomecolumnsinatableAthatdonothaveanentryintableB.HowcanIachievethatinHive?【发布时间】：2019-10-3016:28:13【问题描述】：我想在表(A)中提取一些在... 查看详情