• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1796
  • Last Modified:

B Tree Formulas

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?
2 Solutions
slightwv (䄆 Netminder) Commented:
Unfortunately we are not allowed to provide answers to homework/exam questions.

Please review:
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.
Jim Dettman (Microsoft MVP/ EE MVE)President / OwnerCommented:
<<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.


Incidentally the data is only 3.4 Megabytes. It and all possible keys would fit into memory these days.
JCW2Author Commented:
Thank you for your help.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now