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

x
Solved

# B Tree Formulas

Posted on 2011-05-08
Medium Priority
1,731 Views

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?
0
Question by:JCW2

LVL 78

Expert Comment

ID: 35719676
Unfortunately we are not allowed to provide answers to homework/exam questions.

http://www.experts-exchange.com/help.jsp#hs=23&hi=21
0

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 :-

http://www.cs.utsa.edu/~carola/teaching/cs5633/spring06/slides/Lecture-Btrees.pdf

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.
0

LVL 58

Expert Comment

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.

JimD.
0

LVL 27

Assisted Solution

BigRat earned 2000 total points
ID: 35719975
Wow!

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

Author Closing Comment

ID: 35725385
0

## Featured Post

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
###### Suggested Courses
Course of the Month15 days, 2 hours left to enroll