CODEWITHSUNDEEP
algorithm
Rivers Shall
Rivers Shall

Reputation: 561

Using binary search in B-Tree

In the book CLRS(Introduction to algorithms), B-Tree is introduced in Chapter 18. And it has the following property(P488)

the x.n keys themselves, x.key1, ..., x.keyx.n stored in nondecreasing order

But in the procedure for searching an element in B-Tree, inserting an element into B-Tree, CLRS uses linear search instead of binary search in searching for the key in a particular node.

Why does it do that? Would it get better performence with binary search?

Upvotes: 4

Views: 1862

Answers (1)

Sneftel
Sneftel

Reputation: 41474

If you want to allow the order to vary, then you're right: doing a binary search still results in time complexity in O(log n), while doing a linear search results in O(t log n). But if you consider the order (maximum degree) of the B-tree fixed, then whether you do a binary or linear search doesn't matter to the time complexity. Since the order is generally determined by considerations like cache line size, that's a reasonable simplification to make.

In practice, a linear search will often give you better performance because it can be done with less branching and is more amenable to SIMD processing. Actual B-tree implementations will either use only linear search, or an initial binary search followed by a linear search. The wall-clock time spent searching will be dominated by the time waiting to fetch nodes, not by the search for the appropriate children.

Upvotes: 1

Related Questions