Re: B+ Tree and its concept

On 2006-10-08, accpactec_at_hotmail.com wrote:

> So interms of I/O, since the b+ tree is stored in a file, if we want
> to access multiple data record, are we going to have multiple reads of
> the b+ tree file or is it that once you read the file, everything is
> held in memory and therefore, reducing the number of IOs.

The B+ tree is used precisely because it is suitable for situations where the tree grows so large that it need not fit into available memory. Thus, you'd generally expect to be doing multiple I/O's. Often it does happen that a B+ tree is used even when it in fact fits into memory, and then your cache manager might keep it there permanently. But this is a special case, not the general one, and caching policy is a separate from B+ tree maintenance as such.

> also how is the order determined?

Normally the block size determines the order. You have a tradeoff between a) extraneous data brought into memory and naively searched because accessing any index entry on a page necessarily brings in the whole page and b) seek latency, which means that bringing in a large contiguous page of index entries is often quite cheap while fetching another page might incur a large penalty. B+ trees are used because they are of high order, this massively cuts down on the depth of the tree, and since seek latency is only incurred when crossing from one level of the tree to the next, we can trade in cheap data movement and in-core searching for much slower random seeks. Practical concerns lead to B+ tree pages the size of an operating system cache block (often 4K) or some smallish multiple of it, because that makes interfacing a lot easier and it's usually large enough to reap most of the benefits of a shallower tree. The chosen block size then limits the number of index entries that will fit on a page, and thereby the order.

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2