数据库如何在B树/B+树中存储数据

7
我的问题是数据库如何存储数据,并在内部执行查询。
假设我们的表中有以下字段:
- ID - Name - Age - Weight - Manager 并且我们查询`select * from Table1 where age>50 and weight<100`
我只是好奇它在内部如何执行查询。
在这个示例中,B-Tree/B+Tree的节点包含什么呢?
1个回答

6
您选择的示例是少数几种情况之一,单个树无法完成任务(两个独立范围)。
然而,我正在编写的电子书的第一章解释了B-Tree索引的内部工作原理:http://use-the-index-luke.com/anatomy/ 编辑更多关于为什么对于上述示例可能需要两个索引的细节。
上述查询可以由三种可能的索引配置支持:
1. 在AGE上连接索引,然后在WEIGHT上连接索引(按此顺序)。 如果查询读取所有记录WHERE AGE & gt; 50,然后按WEIGHT过滤。
2. 在WEIGHT上连接索引,然后在AGE上连接索引(另一种顺序)。 这样做的方式不同:读取所有记录WHERE WEIGHT & lt; 100,然后按AGE过滤。
无论哪种方法更有效取决于您拥有的数据。如果记录少于 AGE > 50 ,则第一个查询将更有效,否则第二个查询将更有效。但是,如果您使用不同的值进行查询,则情况可能会改变。
连接索引无法很好地支持查询的原因是每个索引顺序仅在一个轴上。每个索引条目在另一个条目之前或之后,但从未相邻。所有索引条目构建一个链。
具有两个独立范围查询的查询将需要两个轴,而不是像棋盘一样的链。一个轴用于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环境,则可能仍需要位图索引。

附注: 在我的书中,索引AGE是一个练习(带解决方案)--特别是因为存储AGE是一个不好的做法,你应该存储出生日期。


嗨,马库斯,我已经浏览了你正在进行中的电子书链接。你解释得非常清楚,做得很好。我明白了索引是如何在内部存储的,但是根据我的原始问题,我们是否需要两个索引来处理这种范围查询呢? - ZeNo
嗨,我猜这个框框对我的回答来说可能有点小,所以我已经稍微编辑了一下上面的内容。 - Markus Winand
谢谢马库斯提供如此简洁明了的解释。我现在感觉茅塞顿开 :) - ZeNo
1
你没有提到空间索引,如r树或映射在常规树上的空间填充曲线。这些类型的索引是多维的,并支持您需要的所有范围搜索。 - boneill

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接