mysql - 数据库如何在 B-Tree/B+Tree 内部存储数据

Question

我的问题是数据库如何存储数据以及它如何在内部执行查询。

假设我们的表中有以下字段:

1. 身份证
2. 姓名
3. 年龄
4. 体重
5. 经理

然后我们查询select * from Table1 where age>50 and weight<100

我只是好奇它是如何在内部执行查询的。

这个例子中B-Tree/B+Tree的Node会包含什么？

Answer 1

您选择的示例是单个树无法完成工作(两个独立范围)的少数情况之一。

但是，我正在编写的电子书的第一章解释了 B 树索引的内部工作原理:http://use-the-index-luke.com/anatomy/

EDIT 以了解为什么两个索引可能对上述示例有用的更多详细信息。

上述查询可以通过三种可能的索引配置来支持:

1. AGE 上的串联索引然后 WEIGHT (按此顺序)。
   以防万一，查询将读取所有记录 WHERE AGE > 50然后按 WEIGHT 过滤.

2. WEIGHT 上的串联索引然后 AGE (其他顺序)。
   情况不同:读取所有记录 WHERE WEIGHT < 100然后按 AGE 过滤.

哪个更有效取决于您拥有的数据。如果记录少AGE > 50比WEIGHT < 100第一个会更有效率，否则第二个。但是，如果您使用不同的值进行查询，情况可能会发生变化。

连接索引不能很好地支持查询的原因是每个索引顺序仅在一个轴上。每个索引条目都在另一个索引条目之前或之后，但绝不会紧挨着它。所有索引条目构成一条链。

具有两个独立范围查询的查询需要两个轴，不像链条，而更像棋盘。一个轴 AGE另一个为WEIGHT .如果可能的话，您的查询将只需要扫描棋盘的一个角。

但是，B 树只有一个轴，因此您必须首先选择要使用的标准。如果您选择 AGE这意味着从 AGE 50 开始, 整个链将被扫描直到结束。只有存储在链侧的一些记录也符合 WEIGHT < 100 的条件。 , 其他记录必须被读取但将被丢弃。

所以，说来话长，解释为什么一棵树不能支持带有两个独立范围子句的查询。另一方面，一个连接索引可以很好地完成以下工作:

WHERE age = 50 AND weight < 100
WHERE weight = 100 AND age > 50
WHERE age > 50 AND age < 70;

但是，如果在两个不同的列上使用两个不等运算符，就会出现问题。

那么，怎么办？

第三种可能的方法是在两列上有两个独立的索引。这允许拥有任意数量的轴(只需创建更多索引)。然而，这也存在一些巨大的问题。首先，并非所有 DB 产品都支持它。只要它受到支持，它就是一个相当广泛的操作。它通常以扫描每个索引的方式工作，为每个结果构建一个位图索引。然后连接这些位图索引以应用 AND运算符(operator)。这是大量的数据处理——只有当每个条件对其自身的选择性不是很强时，才值得付出努力，但两者加起来都非常有选择性。

不需要我的建议吗？

如果您的查询在 OLTP 环境中运行:使用一个串联索引。 两个独立的索引只是最后的选择。但是，如果您在 OLAP 环境中工作，您可能无论如何都需要位图索引。

附言: 索引 AGE是一个exercise在我的书中(有解决方案)——特别是因为存储 AGE是一种不好的做法，您应该存储出生日期。