Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium


B Tree Formulas

Posted on 2011-05-08
Medium Priority
Last Modified: 2012-05-11
The Problem
g. Suppose that the file is not ordered by the key field Ssn and we want to construct a B+-tree access structure (index on SSn. Calculate (i) the orders p and p_leaf of the B+-tree; (ii) the number of leaf-level blocks needed if if blocks are approximately 69 percent full (rounded up for convenience); (iii) the number of levels needed if internal nodes are also 69 percent full (rounded up for convenience); (iv) the total number of blocks required by the B+-tree; and (v) the number of block accesses needed to search for and retrieve a record from the file - given its Ssn value - using the B+-tree.

h. Repeat part g, but for a B-tree rather than for a B+-tree. Compare your results for the B-tree and for the B+tree.

Formula for order p of a B+ tree:

(p * P) + ((p - 1) * V) < B

Formula for p_leaf of a B+ tree:

(p_leaf * (Pr * V)) + P < B

I'm thinking about part h. Here, I need a formula of some kind for a B tree. Can you help me in some way?
Question by:JCW2
LVL 78

Expert Comment

by:slightwv (䄆 Netminder)
ID: 35719676
Unfortunately we are not allowed to provide answers to homework/exam questions.

Please review:
LVL 27

Accepted Solution

BigRat earned 2000 total points
ID: 35719815
There are masses of analyses for B-Trees (as k-ary trees) on the web, here's one :-


Incidentally how old is this question? A block size of 512 bytes comes out of the eighties. Today you don't get clusters less than 32K.
LVL 58
ID: 35719921
<<Incidentally how old is this question? A block size of 512 bytes comes out of the eighties. Today you don't get clusters less than 32K. >>

  Disk cluster yes, but many DBMS's operate with blocking other then disk cluster size.  OpenVMS still operates with blocking of 512 bytes to this day for everything.

LVL 27

Assisted Solution

BigRat earned 2000 total points
ID: 35719975

Incidentally the data is only 3.4 Megabytes. It and all possible keys would fit into memory these days.

Author Closing Comment

ID: 35725385
Thank you for your help.

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What we learned in Webroot's webinar on multi-vector protection.
Microsoft Jet database engine errors can crop up out of nowhere to disrupt the working of the Exchange server. Decoding why a particular error occurs goes a long way in determining the right solution for it.
This lesson discusses how to use a Mainform + Subforms in Microsoft Access to find and enter data for payments on orders. The sample data comes from a custom shop that builds and sells movable storage structures that are delivered to your property. …
Loops Section Overview

577 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question