标签: b-tree

我有一个大型数据库来解决填字游戏,包括一个单词和一个描述.我的应用程序允许搜索特定长度的单词和特定位置上的字符(这是通过艰难的方式完成的...仔细阅读所有单词并检查每个单词).加上描述搜索(如有必要)

例如找到单词_ _ A _ _ B(6个字母,第三个字符A和最后一个B)

我想以这样的方式索引单词,以便搜索速度非常快.我的第一个想法是使用平衡树结构,任何其他建议？

在我看来,将数据作为文件存储在B树中的一种方法可以使用带有结构序列(数组)的二进制文件来有效地完成,每个结构代表一个节点.因此,可以使用与使用数组创建链接列表类似的方法来连接各个节点.但后来支持的问题是删除一个节点,因为在一个巨大的文件中只删除中间的几个字节是不可能的.

一种删除方法可以是跟踪"空"节点,直到达到阈值截止,然后制作另一个将丢弃空节点的文件.但这很乏味.

从简单/效率的角度来看,是否有更好的方法来删除,甚至在文件中表示B树？

TIA,-Sviiya

b树和b +树只能在他们的叶子上存储数据吗？我假设他们使用内部节点来搜索所需的数据.

是这种情况还是他们在每个节点中存储数据？

是2n吗？只是检查.

我试图理解在使用BerkeleyDB时应该选择哪种访问方法:B-Tree与HashTable.Hashtable提供O(1)查找,但插入是昂贵的(使用线性/可扩展散列我们得到分摊O(1)插入).但B-Trees提供log N(base B)查找和插入时间.B-Tree还可以支持范围查询并允许按排序顺序进行访问.

1. 除了这些考虑因素还应考虑其他因素吗？
2. 如果我不需要支持范围查询,我可以使用Hashtable访问方法吗？

我正在尝试为我的迭代器和const_iterator类实现一个反向迭代器适配器,但有点麻烦.如果有人能指导我完成这一点,那将非常感激!

我的想法是我应该能够从我的rbegin()和rend()函数调用中创建一个反向迭代器

reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;

我在课堂上使用以下typedef:

typedef btree_iterator<T> iterator;
typedef const_btree_iterator<T> const_iterator;
typedef reverse_btree_iterator<iterator> reverse_iterator;
typedef reverse_btree_iterator<const_iterator> const_reverse_iterator;

如您所见,我希望能够使用模板创建反向迭代器,为reverse_iterator类提供迭代器或const_iterator.

不幸的是,有点我坚持......

下面是我目前拥有的类定义,但有错误.

template <typename I> class reverse_btree_iterator {

  typedef ptrdiff_t                     difference_type;
  typedef bidirectional_iterator_tag    iterator_category;

public:

  reverse_btree_iterator() : base_(I()) {}
  template <typename T> reverse_btree_iterator(const btree_iterator<T>& rhs) : base_(rhs) {}

  I base() { return base_; }

  I::reference operator*() const;
  I::pointer operator->() const;
  I& operator++();
  I operator++(int);
  I& operator--();
  I operator--(int);
  bool operator==(const I& other) const;
  bool …

我对2-3-4树在操作后如何维持高度平衡属性操作有了基本的了解,以确保即使最坏的情况操作也是O(n logn).

但我不明白它知道为什么只有2-3-4？

为什么不2-3或2-3-4-5等？

我正在尝试使用以下顺序创建B +树,

10 20 30 40 50 60 70 80 90 100

所有索引节点应至少有2个,最多3个密钥.我能够插入到90,但插入100后它会将高度从2增加到3.

问题是root的第二个子节点有一个节点,我无法修复它.应该至少有2个,对吧？有人可以指导我吗？

更新:我正在遵循这个算法

If the bucket is not full (at most b - 1 entries after the insertion), add the record.
Otherwise, split the bucket.
Allocate new leaf and move half the bucket's elements to the new bucket.
Insert the new leaf's smallest key and address into the parent.
If the parent is full, split it too.
Add the middle key to the parent node.
Repeat until …

也许这可能是菜鸟,但我正在搞几张桌子.

我有表A约45,000条记录

我有表B大约150万条记录

我有一个问题:

update
    schema1.tablea a
    inner join (
        SELECT DISTINCT
            ID, Lookup,
            IDpart1, IDpart2
        FROM
            schema1.tableb
        WHERE
            IDpart1 is not NULL
        AND
            Lookup is not NULL
        ORDER BY
            ID,Lookup
    ) b Using(ID,Lookup)
set 
    a.Elg_IDpart1 = b.IDpart1, 
    a.Elg_IDpart2 = b.IDpart2
where
    a.ID is NOT NULL
AND
    a.Elg_IDpart1 is NULL

所以我在ID,Lookup上强制索引.每个表都有这些列的索引,但由于子查询我强制它.

它正在运行,它真的应该采取,我想在5分钟之内......

我的问题是关于索引,而不是查询.

我知道你不能在有序索引中使用哈希索引.

我目前在ID,Lookup上都有索引,并且作为一个索引,它是一个B-Tree索引.基于我的WHEREClause,哈希索引是否适合作为优化技术？

我可以有一个哈希索引,其余的索引是B树索引吗？

这不是主要关键字段.

我会发布我的解释,但我更改了这些表上的名称.基本上它只是为ID使用索引...而不是使用ID,Lookup,我想强制它使用它们,或者至少把它变成另一种索引,看看是否有帮助？

现在我知道MySQL足够聪明,可以确定哪个索引最合适,那么它正在做什么？Lookup字段映射ID的第一部分和第二部分......

对此有任何帮助或见解表示赞赏.

 UPDATE

一个EXPLAIN在UPDATE我拿出子查询后.

+----+-------------+-------+------+-----------------------------+--------------+---------+-------------------+-------+-------------+
| id | select_type | table | type |        possible_keys        | …

我正在观看有关 B+ 树基础知识的视频，他提到 B+ 树叶子存储在磁盘上，除了root存储在main memory. 我的教授在课堂上提到索引存储在 中main memory，并且leaves包含指向磁盘的数据指针。

见下图：

我的问题是所有索引到底存储在哪里？

• 我们是否只将根存储在主内存中？
• 所有索引都存储在主存中？

我已经浏览了几个链接，但没有人明确提到这部分？谁能澄清我的问题。谢谢