在 Rust 中过滤/查询多键B树索引

Question

在 Rust 中过滤/查询多键B树索引

3

我想在一个内存数据库中，使用BTreeMap作为索引，支持多个关键字。就像这样：

let mut map = BTreeMap::new();
map.insert(("a".to_string(), "x".to_string()), "ax".to_string());
map.insert(("a".to_string(), "y".to_string()), "ay".to_string());

现在我的问题是，实际上查询这个的最佳方式是什么？例如，我想要获取（“a”，*），也就是所有以“a”为第一个键并且第二个键任意的条目。

我尝试了类似于以下内容：

use std::{collections::{BTreeMap}, cmp::Ordering};
use std::ops::Bound::{Included, Unbounded};

#[derive(Clone, Debug, Hash)]
pub enum StringKey {
    Exact(String),
    Any,
}
impl PartialOrd for StringKey {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        match (self, other) {
            (StringKey::Exact(a), StringKey::Exact(b)) => Some(a.cmp(b)),
            (StringKey::Exact(_), StringKey::Any) => Some(Ordering::Equal),
            (StringKey::Any, StringKey::Exact(_)) => Some(Ordering::Equal),
            (StringKey::Any, StringKey::Any) => Some(Ordering::Equal),
        }
    }
}
impl Ord for StringKey {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}
impl PartialEq for StringKey {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Self::Exact(a), Self::Exact(b)) => a == b,
            (Self::Exact(_), Self::Any) => true,
            (Self::Any, Self::Exact(_)) => true,
            (Self::Any, Self::Any) => true,
        }
    }
}
impl Eq for StringKey {
}

fn main() {
    let mut map = BTreeMap::new();
    map.insert((StringKey::Exact("a".to_string()), StringKey::Exact("x".to_string())), "ax".to_string());
    map.insert((StringKey::Exact("a".to_string()), StringKey::Exact("y".to_string())), "ay".to_string());
    map.insert((StringKey::Exact("b".to_string()), StringKey::Exact("x".to_string())), "bx".to_string());
    let query = (StringKey::Exact("a".to_string()), StringKey::Any);
    // Would be easier to do (Included(query), Included(query)), but that only returns one item
    let iter = map.range((Included(query.clone()), Unbounded)); 
    for (key, value) in iter {
        if key > &query {
            return;
        }
        println!("{:?} {:?}", key, value);
    }
}

打印哪些内容

(Exact("a"), Exact("x")) "ax"
(Exact("a"), Exact("y")) "ay"

这么做是有效的，但问题在于我违反了 Ord/Eq 规则（例如 StringKey::Exact("a") == StringKey::Any == StringKey::Exact("b")），这似乎不是正确的方法。而且当我希望在代码的其他部分中将 StringKey 存储在 HashMap 中时，由于实现 Eq 的方式，这并不真正起作用。

那么，有更好的方法吗？

感谢任何帮助！

- Fredrik Norén

2个回答

0

对于过滤，匹配元组模式可能已经足够了。

以下是一个简单的例子：

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert(("a", "x"), "ax");
    map.insert(("a", "y"), "ay");
    map.insert(("b", "y"), "by");
    for (k, v) in &map {
        if matches!(k, ("a", _)) {
            println!("{:?} -> {}", k, v);
        }
    }
}

游乐场

使用范围的解决方案更加优雅（可能也更高效）。但它也更加复杂。因此，这将取决于您的需求。

- Netwave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- apilat · Accepted Answer

你目前的实现违反了Ord的契约。这意味着您唯一可以可靠地说调用 map.range() 不会破坏内存安全。该函数返回的值，或者它是否返回而不是触发崩溃，在rust的不同版本中可能会改变，不能依赖它们。简而言之，你确实希望你的Ord实现是一个完全序。

解决问题（也很好地符合range接口的规范）的最佳方法是有两个特殊值-Min和Max。然后对于("a", *)的查询将有效地转换为("a", Min) .. ("a", Max)。

use std::{collections::BTreeMap, cmp::Ordering};
use std::ops::Bound::{Included, Unbounded};

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum StringKey {
    Min,
    Exact(String),
    Max,
}

fn main() {
    let mut map = BTreeMap::new();
    map.insert((StringKey::Exact("a".to_string()), StringKey::Exact("x".to_string())), "ax".to_string());
    map.insert((StringKey::Exact("a".to_string()), StringKey::Exact("y".to_string())), "ay".to_string());
    map.insert((StringKey::Exact("b".to_string()), StringKey::Exact("x".to_string())), "bx".to_string());
    
    let query_min = (StringKey::Exact("a".to_string()), StringKey::Min);
    let query_max = (StringKey::Exact("a".to_string()), StringKey::Max);
    let iter = map.range(query_min..query_max); 
    for (key, value) in iter {
        println!("{:?} {:?}", key, value);
    }
}