B-树：文件组织的标准利器

需积分: 9 163 浏览量更新于2024-07-23 收藏 1.31MB PDF 举报

"《无处不在的B树：数据库存储的基石》本文档由道格拉斯·科默撰写，探讨了B树在计算机科学领域的广泛应用。随着大型计算机系统的兴起，B树已经成为文件组织的标准方式，无论是用户文件索引、专用数据库系统还是通用访问方法，都广泛采用B树技术。B树的设计初衷是为了提高数据检索效率，它能够在二级存储设备上有效地管理大量信息。文章首先回顾了B树的基本概念，这种数据结构的特点在于其自我平衡的特性，允许快速查找、插入和删除操作。B树通常具有多级节点，每个节点可以包含多个子节点和键值对，这使得它在处理大量数据时展现出优异的性能。 B+树是B树的一种变体，特别是值得关注的重点。相比于普通B树，B+树的所有数据都存储在叶子节点，而内部节点只用于索引，这样减少了磁盘I/O次数，特别适合磁盘读取密集型应用。B+树的这个特性使其在文件系统和数据库管理系统中大受欢迎，因为它能有效减少外部寻址，提高数据访问速度。此外，文中还对比了B树与B+树的不同优缺点，分析了每种实现方式的适用场景和成本。B树可能更适合频繁的插入和删除操作，而B+树则在随机访问性能上有优势。作者通过一个通用的访问方法示例，展示了如何利用B树进行高效的数据访问。关键词包括：B树、B+树、B*树、文件组织、索引。这篇文章被归类在数据库管理（3.73）、数据库系统（3.74）、数据结构（4.33）以及文件系统设计（43434）等多个领域，突显了B树在现代信息技术中的核心地位。本文深入解析了B树在文件组织中的关键作用，以及不同变体的特性比较，为理解和优化大型系统中的数据存储提供了有价值的见解。"

124 • D. Comer

Recall that in a binary search tree the

branch taken at a node depends on the

outcome of a comparison of the query key

and the key stored at the node. If the query

is less than the stored key, the left branch

is taken; if it is greater, the right branch is

followed. Figure 2 shows part of such a tree

used to store employee numbers, and the

path taken for the query "15."

Now consider Figure 3 which shows a

modified search tree with two keys stored

in each node. Searching proceeds by choos-

ing one of three paths at each node. In the

figure, the query, 15, is less than 42 so the

leftmost would be taken at the root. For

those queries between 42 and 81 the center

path would be selected, while the rightmost

path would be followed for queries greater

than 81. The decision procedure is repeated

at each node until an exact match occurs

(success) or a leaf is encountered (failure).

In general, each node in a B-tree of order

d contains at most 2d keys and 2d + 1

pointers, as shown in Figure 4. Actually,

the number of keys may vary from node to

node, but each must have at least d keys

and d + 1 pointers. As a result, each node

is at least 1/~ full. In the usual implementa-

tion a node forms one record of the index

f'fle, has a fixed length capable of accom-

modating 2d keys and 2d pointers, and con-

tains additional information telling how

many keys correctly reside in the node.

/ \ / \

FIGURE 2. Part of a binary search tree for employee

numbers The path taken for query "15" is darkened.

I N\

!~2 I,I ~3, I

1 1

FIGURE 3. A search tree with 2 keys and 3 branches

per node. The path taken for query "15" is darkened.

Ugually, large, multikey nodes cannot be

kept in main memory and require an access

to secondary storage each time they are to

be inspected. Later, we will see how, under

our cost criterion, maintaining more than

one key per node lowers the cost of find,

insert, and delete operations.

Balancing

The beauty of B-trees lies in the methods

for inserting and deleting records that al-

ways leave the tree balanced. As in the case

of binary search trees, random insertions of

records into a file can leave a tree unbal-

anced. While an unbalanced tree, like the

one shown in Figure 5a has some long paths

and some short ones, a balanced tree, like

the one shown in Figure 5b, has all leaves

at the same depth. Intuitively, B-trees have

a shape as shown in Figure 6. The longest

path in a B-tree of n keys contains at most

about logdn nodes, d being the order of the

B-tree. A find operation may visit n nodes

FIGURE 4. A node in a B-tree of order d with 2d

keys and 2d + 1 pointers.

I,, , -, \1

I/t',

--1

I/i,, \1

I/ \ -..I

--....

(b)

FIGURE 5. (a) An unbalanced tree with many long

paths, and (b) a balanced tree with all paths to

leaves exactly the same length.

Computing Surveys, Vol 11, No 2, June 1979

剩余16页未读，继续阅读

羊德馨

粉丝: 0
资源: 6

B-树：文件组织的标准利器

B-Tree 文件组织：成功的原因与变种分析

B-树：文件组织的标准选择

智能手机间共享图像的Ubiquitous-Media-Sharing-Surface系统

The Ubiquitous B-Tree

Ubiquitous-Wind-Tracking

ubiquitous-octo-guacamole

ubiquitous-octo-fortnight

ubiquitous-octo-eureka:CDA

Ubiquitous-Media-Sharing-Surface:在共享表面上的智能手机之间交换图像

ubiquitous-journey

最新资源