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

Question

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

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

1. ID
2. 名称
3. 年龄
4. 重量
5. 经理

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

我很好奇它是如何在内部执行查询的.

在这个例子中,B-Tre/B + Tree的节点包含什么？

Answer 1

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

然而,我正在进行的电子书的第一章解释了B-Tree索引的内部工作原理:http://use-the-index-luke.com/anatomy/

编辑更多详细信息,为什么两个索引可能对上面的示例有用.

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

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;

但是,如果在两个不同的列上使用两个不等运算符,则会出现问题.

那么该怎么办？

第三种可能的方法是在两列上有两个独立的索引.这允许拥有任意多个轴(只需创建更多索引).但是,这有一些很大的问题.首先,并非所有数据库产品都支持这一点.只要它得到支持,它就是一个相当广泛的操作.它通常以扫描每个索引的方式工作,为每个结果构建位图索引.然后连接这些位图索引以应用AND运算符.这是很多数据的重复 - 如果每个条件对它自己都没有很大的选择性,那么它是值得的,但两者都是非常有选择性的.

不是我的建议吗？

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

ps:索引AGE是我书中的练习(有解决方案) - 特别是因为存储AGE是一种不好的做法,你应该存储出生日期.