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

Question

我正在尝试使用 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 时，这并不起作用。

那么，再一次；有一个更好的方法吗？

感谢您的帮助！

Answer 1

您当前的实现违反了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);
    }
}