AAs Wonder Works

btreestest

2010-05-10T07:49:00.001-07:00

LACROSSE UNIVERSITY

B-Trees

A PAPER SUBMITTED TO

THE FACULTY OF THE DIVISON OF SCIENCES

IN CANDIDACY FOR THE DEGREE OF

MASTER OF SCIENCE

DEPARTMENT OF COMPUTER SCIENCE

Ayesha Asghar

December 18, 2006

To Zainab

If we believe in data structures, we must believe in independent (hence simultaneous) processing. For why else would we collect items within a structure? Why do we tolerate languages that give us the one without the other?

Epigrams in Programming

CONTENTS

ILLUSTRATIONS................. vi

PREFACE................. vii

ACKNOWLEDGEMENTS................. viii

1. Introduction 1

1.1. Purpose 1

1.2. Scope 1

2. B-Trees 2

2.1. Structure of B Trees 2

2.2. Height of B Trees 4

2.3. Operations on B Trees 5

2.3.1. B-Tree Search 5

2.3.2. B-Tree Create 6

2.3.3. B-Tree Split-Child 7

2.3.4. B-Tree Insert 8

2.3.5. B-Tree Insert-Nonfull 8

2.3.6. B-Tree-Delete 9

3. B-Trees Examples 10

3.1. B-Tree Insert 10

3.2. B-Tree Delete 13

4. Implementing B-Trees 19

5. Application of B-Trees 22

5.1. Databases 22

5.2. Concurrent Access to B-Trees 23

6. Variants of B-Trees 25

6.1. B⁺-Trees 25

6.2. B^*-Trees 25

6.3. Trade offs 25

7. Conclusion 26

Bibliography................. 28

ILLUSTRATIONS

Figure Page

1. Structure of B-Trees

2. Height of B Trees

3. B-Tree-Search(x, k)

4. B-Tree-Create(T)

5. B-Tree-Split-Child(x, i, y)

6. B-Tree-Insert(T,k)

7. B-Tree-Nonfull(x,k)

8. Initial B-Tree

9. After inserting ‘17’

10. After inserting ‘6’

11. After inserting ‘21’

12. Inserting ‘67’

13. After inserting ‘67’

14. B-Tree Deletion example

15. B-Tree Deletion Case 1

16. B-Tree Deletion Case 2

17. B-Tree Class Definition

18. BTree Class Insert Member Function Definition

19. BTree Class InsertPair Member Function Definition

PREFACE

The aim of this Applied Knowledge Paper is to give a deep insight on the need, concepts and application of B-Trees.

The document starts by giving a brief introduction to B-Trees. It entails the structure of B-Trees and gives a comprehensive definition for it.

Further the operations on B-Trees have been discussed in details. The algorithm/code for these operations has been provided as well for a better understanding.

Next to this, comprehensive examples of the operations on B-Trees have been given. And then the application of the B-trees has been talked about, where the uses and advantage of B-Trees have been stressed upon. Next the different variations of B-Trees are elucidated.

Finally, the document wraps up the paper by critically evaluating merits and demerits of B-Trees. The author of the paper hopes that this discussion will serve as a comprehensive guideline for the readers.

ACKNOWLEDGEMENTS

I would like to thank the auspicious instructors of Lacrosse University under whose guidance I’ve been able to come up with this report. I thank them for their cooperation through out and also for resolving all problems and every issue that I faced.

Next, I would like to thank my family who provided me with all the sources and material required for making this possible. Lastly; I would like to thank God Almighty who gave me the strength and will power to complete this piece of work.

1. Introduction

1.1. Purpose

The purpose of this paper is to describe a well-formed and a thorough analysis of the B-Trees. This paper also gives an introduction into the structure of B-Trees with detailed examples.

It focuses on the operations on B-Trees and discusses in-detail their structure with help of extensive examples.

This paper provides an understanding of the need and benefits of B-Trees and also concentrates on its application. The variations of B-Trees have also been discussed.

This paper will assist the novice programmers to have a better understanding of B-Trees and its operations implemented and its uses. While, the expert programmers will also agree upon the concept details provided.

1.2. Scope

The paper provides answers to what, when, how and who questions related to B-Trees, such as:

§ What is a B-Tree?

§ What is the height of a B-Tree?

§ What are the operations supported by B-Trees?

§ Applications of B-Trees.

§ Variants of B-Trees.

2. B-Trees

Tree structures support various basic dynamic set operations including Search, Predecessor, Successor, Minimum, Maximum, Insert, and Delete in time proportional to the height of the tree. Ideally, a tree will be balanced and the height will be log n where n is the number of nodes in the tree. To ensure that the height of the tree is as small as possible and therefore provide the best running time, a balanced tree structure like a red-black tree, AVL tree, or b-tree must be used.

When working with large sets of data, it is often not possible or desirable to maintain the entire structure in primary storage (RAM). Instead, a relatively small portion of the data structure is maintained in primary storage, and additional data is read from secondary storage as needed. Unfortunately, a magnetic disk, the most common form of secondary storage, is significantly slower than random access memory (RAM). In fact, the system often spends more time retrieving data than actually processing data.

B-trees are balanced trees that are optimized for situations when part or the entire tree must be maintained in secondary storage such as a magnetic disk. Since disk accesses are expensive (time consuming) operations, a b-tree tries to minimize the number of disk accesses. For example, a b-tree with a height of 2 and a branching factor of 1001 can store over one billion keys but requires at most two disk accesses to search for any node (Cormen et al. 1998, p. 384).

2.1. Structure of B Trees

Unlike a binary-tree, each node of a b-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Each key has an associated child that is the root of a sub-tree containing all nodes with keys less than or equal to the key but greater than the preceding key. A node also has an additional rightmost child that is the root for a sub-tree containing all keys greater than any keys in the node.

A b-tree has a minimum number of allowable children for each node known as the minimization factor. If t is this minimization factor, every node must have at least t - 1 keys. Under certain circumstances, the root node is allowed to violate this property by having fewer than t - 1 keys. Every node may have at most 2t - 1 keys or, equivalently, 2t children.

Since each node tends to have a large branching factor (a large number of children), it is typically necessary to traverse relatively few nodes before locating the desired key. If access to each node requires a disk access, then a b-tree will minimize the number of disk accesses required. The minimization factor is usually chosen so that the total size of each node corresponds to a multiple of the block size of the underlying storage device. This choice simplifies and optimizes disk access. Consequently, a b-tree is an ideal data structure for situations where all data cannot reside in primary storage and accesses to secondary storage are comparatively expensive (or time consuming).

In short, A B-tree of order m is an ordered tree which satisfies the following properties:

§ Every node has at most m children.

§ Every node, except the root, has at least m/2 children.

§ The root has at least 2 children.

§ All leaves occur on the same level.

B-trees were introduced by Bayer and McCreight in 1972 (they did not explain their choice of name). They are balanced search trees designed to work well on magnetic disks or other direct-access secondary storage devices. B-trees are similar to red-black trees in that every n-node B-tree has height O(lg n), although the height of a B-tree can be considerably less than that of a red-black tree because its branching factor can be much larger. Therefore, B-trees can also be used to implement many dynamic-set operations in time O(lg n).

The standard representation adopted here is a sequence of number of children of each internal node, where the nodes are traversed bottom-up level-by-level and from right-to-left within a level. See the following figure for an example:

Fig. 1. Structure of B-Trees

This is a B-tree of order 4.

2.2. Height of B Trees

For n greater than or equal to one, the height of an n-key b-tree T of height h with a minimum degree t greater than or equal to 2,

Fig. 2. Height of B Trees

For a proof of the above inequality, refer to (Cormen et al. 1998, pp. 383-384)

The worst case height is O(log n). Since the "branchiness" of a b-tree can be large compared to many other balanced tree structures, the base of the logarithm tends to be large; therefore, the number of nodes visited during a search tends to be smaller than required by other tree structures. Although this does not affect the asymptotic worst case height, b-trees tend to have smaller heights than other trees with the same asymptotic height.

2.3. Operations on B Trees

The algorithms for the search, create, and insert operations are shown below. Note that these algorithms are single pass; in other words, they do not traverse back up the tree. Since b-trees strive to minimize disk accesses and the nodes are usually stored on disk, this single-pass approach will reduce the number of node visits and thus the number of disk accesses. Simpler double-pass approaches that move back up the tree to fix violations are possible.

Since all nodes are assumed to be stored in secondary storage (disk) rather than primary storage (memory), all references to a given node be preceded by a read operation denoted by Disk-Read. Similarly, once a node is modified and it is no longer needed, it must be written out to secondary storage with a write operation denoted by Disk-Write. The algorithms below assume that all nodes referenced in parameters have already had a corresponding Disk-Read operation. New nodes are created and assigned storage with the Allocate-Node call. The implementation details of the Disk-Read, Disk-Write, and Allocate-Node functions are operating system and implementation dependent.

2.3.1. B-Tree Search

The search operation on a b-tree is analogous to a search on a binary tree. Instead of choosing between a left and a right child as in a binary tree, a b-tree search must make an n-way choice. The correct child is chosen by performing a linear search of the values in the node. After finding the value greater than or equal to the desired value, the child pointer to the immediate left of that value is followed. If all values are less than the desired value, the rightmost child pointer is followed. Of course, the search can be terminated as soon as the desired node is found. Since the running time of the search operation depends upon the height of the tree, B-Tree-Search is O(log_t n).

i <- 1

while i <= n[x] and k > key_i[x]

     do i <- i + 1

if i <= n[x] and k = key_i[x]

     then return (x, i)

if leaf[x]

     then return NIL

     else Disk-Read(c_i[x])

          return B-Tree-Search(c_i[x], k)

Fig. 3. B-Tree-Search(x, k)

2.3.2. B-Tree Create

The B-Tree-Create operation creates an empty b-tree by allocating a new root node that has no keys and is a leaf node. Only the root node is permitted to have these properties; all other nodes must meet the criteria outlined previously. The B-Tree-Create operation runs in time O(1).

x <- Allocate-Node()

leaf[x] <- TRUE

n[x] <- 0

Disk-Write(x)

root[T] <- x

Fig. 4. B-Tree-Create(T)

2.3.3. B-Tree Split-Child

If is node becomes "too full," it is necessary to perform a split operation. The split operation moves the median key of node x into its parent y where x is the i^th child of y. A new node, z, is allocated, and all keys in x right of the median key are moved to z. The keys left of the median key remain in the original node x. The new node, z, becomes the child immediately to the right of the median key that was moved to the parent y, and the original node, x, becomes the child immediately to the left of the median key that was moved into the parent y.

The split operation transforms a full node with 2t - 1 keys into two nodes with t - 1 keys each. Note that one key is moved into the parent node. The B-Tree-Split-Child algorithm will run in time O(t) where t is constant.

z <- Allocate-Node()

leaf[z] <- leaf[y]

n[z] <- t - 1

for j <- 1 to t - 1

     do key_j[z] <- key_j+t[y]

if not leaf[y]

     then for j <- 1 to t

          do c_j[z] <- c_j+t[y]

n[y] <- t - 1

for j <- n[x] + 1 downto i + 1

     do c_j+1[x] <- c_j[x]

c_i+1 <- z

for j <- n[x] downto i

     do key_j+1[x] <- key_j[x]

key_i[x] <- key_t[y]

n[x] <- n[x] + 1

Disk-Write(y)

Disk-Write(z)

Disk-Write(x)

Fig. 5. B-Tree-Split-Child(x, i, y)

2.3.4. B-Tree Insert

r <- root[T]

if n[r] = 2t - 1

     then s <- Allocate-Node()

          root[T] <- s

          leaf[s] <- FALSE

          n[s] <- 0

          c₁ <- r

          B-Tree-Split-Child(s, 1, r)

          B-Tree-Insert-Nonfull(s, k)

     else B-Tree-Insert-Nonfull(r, k)

Fig. 6. B-Tree-Insert(T,k)

2.3.5. B-Tree Insert-Nonfull

To perform an insertion on a b-tree, the appropriate node for the key must be located using an algorithm similar to B-Tree-Search. Next, the key must be inserted into the node. If the node is not full prior to the insertion, no special action is required; however, if the node is full, the node must be split to make room for the new key. Since splitting the node results in moving one key to the parent node, the parent node must not be full or another split operation is required. This process may repeat all the way up to the root and may require splitting the root node. This approach requires two passes. The first pass locates the node where the key should be inserted; the second pass performs any required splits on the ancestor nodes.

Since each access to a node may correspond to a costly disk access, it is desirable to avoid the second pass by ensuring that the parent node is never full. To accomplish this, the presented algorithm splits any full nodes encountered while descending the tree. Although this approach may result in unnecessary split operations, it guarantees that the parent never needs to be split and eliminates the need for a second pass up the tree. Since a split runs in linear time, it has little effect on the O(t log_t n) running time of B-Tree-Insert.

Splitting the root node is handled as a special case since a new root must be created to contain the median key of the old root. Observe that a b-tree will grow from the top.

i <- n[x]

if leaf[x]

     then while i >= 1 and k < key_i[x]

            do key_i+1[x] <- key_i[x]

               i <- i - 1

          key_i+1[x] <- k

          n[x] <- n[x] + 1

          Disk-Write(x)

     else while i >= and k < key_i[x]

            do i <- i - 1

          i <- i + 1

          Disk-Read(c_i[x])

          if n[c_i[x]] = 2t - 1

               then B-Tree-Split-Child(x, i, c_i[x])

                    if k > key_i[x]

                        then i <- i + 1

          B-Tree-Insert-Nonfull(c_i[x], k)

Fig. 7. B-Tree-Nonfull(x,k)

For a better understanding, refer to Section 3.1, where a comprehensive example of B-Tree insertion has been elucidated.

2.3.6. B-Tree-Delete

Deletion of a key from a b-tree is possible; however, special care must be taken to ensure that the properties of a b-tree are maintained. Several cases must be considered. If the deletion reduces the number of keys in a node below the minimum degree of the tree, this violation must be corrected by combining several nodes and possibly reducing the height of the tree. If the key has children, the children must be rearranged. For a detailed discussion of deleting from a b-tree, refer to Section 3.2 and for further comprehensive understanding refer (Cormen et al. 1998, pp 395-397).

3. B-Trees Examples

3.1. B-Tree Insert

For a better understanding of B-Tree insertion operation; let's do a sequence of insertions into this B-tree (M=5, so each node other than the root must contain between 2 and 4 values):

Fig. 8. Initial B-Tree

Step 1: Insert ‘17’

Add it to the middle leaf. No overflow, so it’s done.

Fig. 9. After inserting ‘17’

Step 2: Insert 6

Add it to the leftmost leaf. That overflows, so split it:

Left = [ 2 3 ]
Middle = 5
Right = [ 6 7 ]

Left and Right become nodes; Middle is added to the node above with Left and Right as its children.

Fig. 10. After inserting ‘6’

The node above (the root in this small example) does not overflow, so it’s done.

Step 3: Insert ‘21’

Add it to the middle leaf. That overflows, so split it:

§ left = [ 17 21 ]

§ Middle = 22

§ Right = [ 44 45 ]

Left and Right become nodes; Middle is added to the node above with Left and Right as its children.

Fig. 11. After inserting ‘21’

The node above (the root in this small example) does not overflow, so it’s done.

Step 4: Insert ‘67’

Add it to the rightmost leaf. That overflows, so split it:

Left = [ 55 66 ]
Middle = 67
Right = [ 68 70 ]

Left and Right become nodes; Middle is added to the node above with Left and Right as its children.

Fig. 12. Inserting ‘67’

But now the node above does overflow. So it is split in exactly the same manner:

Left = [ 5 10 ] (along with their children)
Middle = 22
Right = [ 50 67 ] (along with their children)

Left and Right become nodes, the children of Middle. If this were not the root, Middle would be added to the node above and the process repeated. If there is no node above, as in this example, a new root is created with Middle as its only value.

Fig. 13. After inserting ‘67’

The tree-insertion algorithms previously seen add new nodes at the bottom of the tree, and then have to worry about whether doing so creates an imbalance. The B-tree insertion algorithm is just the opposite: it adds new nodes at the top of the tree (a new node is allocated only when the root splits). B-trees grow at the root, not at the leaves. Because of this, there is never any doubt that the tree is always perfectly height balanced: when a new node is added, all existing nodes become one level deeper in the tree.

3.2. B-Tree Delete

Recall the deletion algorithm for binary search trees: if the value to be deleted is in a node having two sub-trees, it would replace the value with the largest value in its left sub-tree and then delete the node in the left sub-tree that had contained the largest value (its guaranteed that this node will be easy to delete).

A similar strategy will be used to delete a value from a B-tree. If the value to be deleted does not occur in a leaf, it is replaced with the largest value in its left sub-tree and then proceeded to delete that value from the node that originally contained it. For example, if 67 is to be deleted from the above tree, the largest value in 67's left sub-tree would be founded, 66, replace 67 with 66, and then delete the occurrence of 66 in the left sub-tree. In a B-tree, the largest value in any value's left sub-tree is guaranteed to be in leaf. Therefore wherever the value to be deleted initially resides, the following deletion algorithm always begins at a leaf.

To delete value X from a B-tree, starting at a leaf node, there are 2 steps:

Remove X from the current node. Being a leaf node there are no sub-trees to worry about.
Removing X might cause the node containing it to have too few values. Recall that the root is required to have at least 1 value in it and all other nodes to have at least (M-1)/2 values in them. If the node has too few values, it is said to have underflowed.

If underflow does not occur, then the deletion process is finished. If it does occur, it must be fixed. The process for fixing a root is slightly different than the process for fixing the other nodes, and will be discussed afterwards.

How to fix a non-root node that has underflowed? Let us take as a specific example, deleting 6 from this B-tree (of degree 5):

Fig. 14. B-Tree Deletion example

Removing 6 causes the node it is in to underflow, as it now contains just 1 value (7). The strategy for fixing this is to try to `borrow' values from a neighbouring node. The current node and its more populous neighbour are joined to form a `combined node' - and in the combined node the value of the parent node should must be included that is in between these two nodes.

In this example, node [7] is joined with its more populous neighbour [17 22 44 45] and put `10' in between them, to create [6 7 10 17 22 44 45].

How many values might there be in this combined node?

§ The parent node contributes 1 value.

§ The node that underflowed contributes exactly (M-1)/2-1 values.

§ The neighbouring node contributes somewhere between (M-1)/2 and (M-1) values.

The treatment of the combined node is different depending on whether the neighbouring contributes exactly (M-1)/2 values or more than this number.

Case 1: Suppose that the neighbouring node contains more than (M-1)/2 values. In this case, the total number of values in the combined node is strictly greater than 1 + ((M-1)/2 - 1) + ((M-1)/2), i.e. it is strictly greater than (M-1). So it must contain M values or more.

The combined node is then to be split into three pieces: Left, Middle, and Right, where Middle is a single value in the very middle of the combined node. Because the combined node has M values or more, Left and Right are guaranteed to have (M-1)/2 values each, and therefore are legitimate nodes. Then value borrowed from the parent is replaced with Middle and Left and Right are used as its two children. In this case the parent's size does not change, so it is completely finished.

This is what happens in the example of deleting 6 from the tree above. The combined node [6 7 10 17 22 44 45] contains more than 3 values, so split it into:

§ Left = [ 6 7 10 ]

§ Middle = 17

§ Right = [ 22 44 45 ]

Then put Middle into the parent node (in the position where the `10' had been) with Left and Right as its children:

Fig. 15. B-Tree Deletion Case 1

Case 2: Suppose, on the other hand that the neighbouring node contains exactly (M-1)/2 values. Then the total number of values in the combined node is 1 + ((M-1)/2 - 1) + ((M-1)/2) = (M-1)

In this case the combined node contains the right number of values to be treated as a node. So it is made into a node and removed from the parent node the value that has been incorporated into the new, combined node. As a concrete example of this case, suppose that, in the above tree, 3 was deleted instead of 6. The node [2 3] underflows when 3 is removed. It would be combined with its more populous neighbour [6 7] and the intervening value from the parent (5) to create the combined node [2 5 6 7]. This contains 4 values, so it can be used without further processing. The result would be:

Fig. 16. B-Tree Deletion Case 2

It is very important to note that the parent node now has one fewer value. This might cause it to underflow - imagine that 5 had been the only value in the parent node. If the parent node underflows, it would be treated in exactly the same way - combined with it’s more populous neighbour etc. The underflow processing repeats at successive levels until no underflow occurs or until the root underflows (the processing for root-underflow is described next).

Now let us consider the root. For the root to underflow, it must have originally contained just one value, which now has been removed. If the root was also a leaf, then there is no problem: in this case the tree has become completely empty.

If the root is not a leaf, it must originally have had two sub-trees (because it originally contained one value). How could it possibly underflow?

The deletion process always starts at a leaf and therefore the only way the root could have its value removed is through the Case 2 processing just described: the root's two children have been combined, along with the root's only value to form a single node. But if the root's two children are now a single node, then that node can be used as the new root, and the current root (which has underflowed) can simply be deleted.

To illustrate this, suppose 7 is deleted from the following B-tree (M=5):

The node [3 7] would underflow, and the combined node [3 10 18 20] would be created. This has 4 values, which is acceptable when M=5. So it would be kept as a node, and `10' would be removed from the parent node - the root. This is the only circumstance in which underflow can occur in a root that is not a leaf. The situation is this:

Clearly, the current root node, now empty, can be deleted and its child used as the new root.

4. Implementing B-Trees

The following contains a class template for elements stored in a B-tree, and a class for a B-tree node, which provides all the methods needed to search, insert, or delete. a sample "main" function is also provided to show how to use the B-tree.

To understand the identifiers and comments, visualize the tree as having its root node at the top of the diagram, its leaf nodes at the bottom of the diagram, and each node as containing an array oriented horizontally, with the smallest element on the left and the largest element on the right.

The zeroth element of a node contains only a sub-tree pointer, no key value or payload.

A b-tree grows "upward", by splitting the root node when the node's capacity is exceeded. Conversely, the depth of the tree is always reduced by merging the last remaining element of the root node with the elements of its two child nodes, so the tree contracts "from the top".

class BTree : public MWayTree

    BTree* parent;

    void InsertPair (Object&, BTree&);

    void AttachKey (unsigned int, Object&);

    void AttachSubtree (unsigned int, MWayTree&);

    Object& InsertKey (unsigned int, Object&);

    BTree& InsertSubtree (unsigned int, BTree&);

    void AttachLeftHalfOf (BTree const&);

    void AttachRightHalfOf (BTree const&, Object&, BTree&);

public:

    BTree (unsigned int);

    BTree (unsigned int, BTree&);

    void Insert (Object&);

    void Withdraw (Object&);

};

Fig. 17. B-Tree Class Definition

void BTree::Insert (Object& object)

    if (IsEmpty ())

        if (parent == 0)

            AttachSubtree (0, *new BTree (m, *this));

            AttachKey (1, object);

            AttachSubtree (1, *new BTree (m, *this));

            numberOfKeys = 1;

        else

            parent->InsertPair (object, *new BTree (m, *parent));

    else

        unsigned int const index = FindIndex (object);

        if (index != 0 && object == *key [index])

            throw invalid_argument ("duplicate key");

        subtree [index]->Insert (object);

Fig. 18. BTree Class Insert Member Function Definition

void BTree::InsertPair (Object& object, BTree& child)

    unsigned int const index = FindIndex (object);

    BTree& extraTree = InsertSubtree (index + 1, child);

    Object& extraKey = InsertKey (index + 1, object);

    if (++numberOfKeys == m)

        if (parent == 0)

            BTree& left = *new BTree (m, *this);

            BTree& right = *new BTree (m, *this);

            left.AttachLeftHalfOf (*this);

            right.AttachRightHalfOf (*this, extraKey, extraTree);

            AttachSubtree (0, left);

            AttachKey (1, *key [(m + 1)/2]);

            AttachSubtree (1, right);

            numberOfKeys = 1;

        else

            numberOfKeys = (m + 1)/2 - 1;

            BTree& right = *new BTree (m, *parent);

            right.AttachRightHalfOf (*this, extraKey, extraTree);

            parent->InsertPair (*key [(m + 1)/2], right);

Fig. 19. BTree Class InsertPair Member Function Definition

For a complete implementation of B-Trees refer to Texteclectric, 2003.

5. Application of B-Trees

5.1. Databases

A database is a collection of data organized in a fashion that facilitates updating, retrieving, and managing the data. The data can consist of anything, including, but not limited to names, addresses, pictures, and numbers. Databases are commonplace and are used everyday. For example, an airline reservation system might maintain a database of available flights, customers, and tickets issued. A teacher might maintain a database of student names and grades.

Because computers excel at quickly and accurately manipulating, storing, and retrieving data, databases are often maintained electronically using a database management system. Database management systems are essential components of many everyday business operations. Database products like Microsoft SQL Server, Sybase Adaptive Server, IBM DB2, and Oracle serve as a foundation for accounting systems, inventory systems, medical recordkeeping systems, airline reservation systems, and countless other important aspects of modern businesses.

It is not uncommon for a database to contain millions of records requiring many gigabytes of storage. For examples, TELSTRA, an Australian telecommunications company, maintains a customer billing database with 51 billion rows (yes, billion) and 4.2 terabytes of data. In order for a database to be useful and usable, it must support the desired operations, such as retrieval and storage, quickly. Because databases cannot typically be maintained entirely in memory, b-trees are often used to index the data and to provide fast access. For example, searching an un-indexed and unsorted database containing n key values will have a worst case running time of O(n); if the same data is indexed with a b-tree, the same search operation will run in O(log n). To perform a search for a single key on a set of one million keys (1,000,000), a linear search will require at most 1,000,000 comparisons. If the same data is indexed with a b-tree of minimum degree 10, 114 comparisons will be required in the worst case. Clearly, indexing large amounts of data can significantly improve search performance. Although other balanced tree structures can be used, a b-tree also optimizes costly disk accesses that are of concern when dealing with large data sets.

5.2. Concurrent Access to B-Trees

Databases typically run in multi-user environments where many users can concurrently perform operations on the database. Unfortunately, this common scenario introduces complications. For example, imagine a database storing bank account balances. Now assume that someone attempts to withdraw $40 from an account containing $60. First, the current balance is checked to ensure sufficient funds. After funds are disbursed, the balance of the account is reduced. This approach works flawlessly until concurrent transactions are considered. Suppose that another person simultaneously attempts to withdraw $30 from the same account. At the same time the account balance is checked by the first person, the account balance is also retrieved for the second person. Since neither person is requesting more funds than are currently available, both requests are satisfied for a total of $70. After the first person's transaction, $20 should remain ($60 - $40), so the new balance is recorded as $20. Next, the account balance after the second person's transaction, $30 ($60 - $30), is recorded overwriting the $20 balance. Unfortunately, $70 has been disbursed, but the account balance has only been decreased by $30. Clearly, this behaviour is undesirable, and special precautions must be taken.

A b-tree suffers from similar problems in a multi-user environment. If two or more processes are manipulating the same tree, it is possible for the tree to become corrupt and result in data loss or errors.

The simplest solution is to serialize access to the data structure. In other words, if another process is using the tree, all other processes must wait. Although this is feasible in many cases, it can place an unnecessary and costly limit on performance because many operations actually can be performed concurrently without risk. Locking, introduced by Gray and refined by many others, provides a mechanism for controlling concurrent operations on data structures in order to prevent undesirable side effects and to ensure consistency.

6. Variants of B-Trees

6.1. B⁺-Trees

Internal nodes contain the indices to the records corresponding to the key values k₁, k₂,..., k_m stored at the internal node. This obviates the need for repeating these key values and associated indices at the leaf level.

More efficient than B-Trees in the case of successful searches.

6.2. B^*-Trees

§ The minimum number of children at each internal node (except the root) is

§ Path lengths are smaller for obvious reasons.

§ Insertions and deletions are more complex.

6.3. Trade offs

B-trees have faster lookup than B+ trees.
In B-tree, non-leaf & leaf are of different sizes.
In B-tree, deletion is more complicated

The traditional implementation for a B-tree uses many pointers (more than one per key), and which can directly affect the performance of the B-tree. So, conclusively, B+ trees are preferred!

7. Conclusion

The B-tree is probably the most popular method in use today for indexes and inverted files in database management systems. B-Trees are often described as a good way to store and retrieve data, especially to and from disk. They're efficient to use and easy to program, and they're often mentioned but not so often discussed. They show up all over the place: In the Berkeley DB_File package, which is (semi-) standard with Perl, and in large high-performance databases. For example, B-Trees are the technology that underlying IBM's well-known VSAM files.

The most important point about B-Trees is that it's easy to implement a version that saves the tree on disk. The tree nodes never need to grow or shrink, so one never has the problem of having to move one to a different place in the file when you insert a key. For this reason, they are frequently used for disk databases where the data have to be accessed by key.

When used in DBM files, B-trees have another big advantage over binary trees - even balanced binary trees. The binary search that occurs in a B-tree node takes about the same amount of CPU time as the binary search on the nodes of a binary tree with the sane number of keys. But when the tree lives on disk, each node must be loaded into memory before it can be examined. In a B-tree, one can adjust B so that each entire node can be loaded with exactly one disk operation, and then searched quickly in memory. In a binary tree, each key resides in its own node, which must be loaded from disk separately. A binary tree therefore typically requires between B/2 and B times as many disk accesses as a B-tree of similar size, because it has fewer keys per node. When the tree lives on the disk, the time to search the tree is dominated by the disk access time, and B-trees are therefore much faster than even balanced binary trees.

DBM files are almost invariably implemented with either B-trees or with hash tables. (Hash tables are the method that Perl uses for regular in-memory hash variables.) However, B-Trees present one enormous advantage over hash tables: The keys are stored in sorted order. Why is this important? Suppose one has a range, and one wants to retrieve all the data for all the keys in that range. One can do this efficiently if the database is stored using B-trees: Locate the two keys corresponding to the upper and lower bounds of the range, and then take all the keys in between. With hash tables, the keys are not stored in any particular order, so there is no "in between," and to retrieve a range of them, you must retrieve all the keys, extract the ones one want, sort them into order, and then query the hash once for each key. That's vastly less efficient.

B-trees have substantial advantages over alternative implementations when node access times far exceed access times within nodes. This usually occurs when most nodes are in secondary storage such as hard drives. By maximizing the number of child nodes within each internal node, the height of the tree decreases, balancing occurs less often, and efficiency increases. Usually this value is set such that each node takes up a full disk block or an analogous size in secondary storage.

Bibliography

[Bayer, 1972]

Bayer, R. Symmetric binary B-trees: Data Structures and maintenance algorithms. Acta Informatica, Volume 1, pp.290-306, 1972.

[Bayer et al, 1972]

Bayer, R and McCreight, E.M. Organization and maintenance of large ordered indexes. Acta Informatica, Volume 1, Number 3, pp. 173-189, 1972.

[Comer, 1979]

Comer, D. The ubiquitous B-tree. ACM Computing Surveys, Volume 11, Number 2, pp 121-137, 1979.

[Cormen et al, 1998]

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, MIT Press, Massachusetts: 1998.

[Kruse, 1987]

Kruse, Robert L. Data Structures & Program Design Second Edition, Prentice-Hall, 1987.

[Kruse et al, 1999]

Kruse, Robert L & Ryba, Alexander J. Data Structures and Program Design in C++, Third Edition, Prentice Hall, 1999.

[Maire, 1998]

Maire, Frederic. (October 18, 1998) An Introduction to B-Trees

http://sky.fit.qut.edu.au/~maire/baobab/lecture/

[Preiss, 1998]

Preiss, Bruno R. (1998) Data Structures and Algorithms with Object-Oriented Design Patterns in Java.

http://www.brpreiss.com/books/opus5/html/page339.html

[Shaffer, 1997]

Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis, Prentice-Hall (1997).

[Tenenbaum et al, 1986]

Tenenbaum, Aaron M. & Augenstein, Moshe J. Data Structures using Pascal. Second Edition, Prentice Hall, 1986.

[Textelectric, 2003]

Texteclectric. (May 9, 2003) Implemeting B-Trees.

http://textelectric.net/btree.html

testing

2008-04-07T07:09:00.000-07:00

Rise of the IT industry

The new millennium has dawned up well concerning the economy and social status of India. The Information Technology in India has grown to an impeccable level in the past 7 years. This has opened up opportunities for millions of Indians in the country and abroad. It has contributed in uplifting the status of most Indians.

Looking at the vast establishments of more and more software companies around the world, it would take about seventy to eighty years for the IT industry to saturate completely. Owing to the good returns in terms of money, most people have shifted their attention towards the IT industry and have started to construct their careers in it. As a result, the number of software engineers in India has grown enormously in this decade. The economy of India has improved to a great extent mainly due to the increase in the number of tax payers from the IT companies. The improvements of Indian multi national companies have roped in a large number foreign clientele. This has definitely contributed to the social development of India.

The development of IT industry has resulted in a lot of adverse effects too. Though the growth has raised the lives of software industries it has pushed the existence of other people steeper. India, basically being a poor nation, has about 90 pc of its population below the red line. These people have been the main sufferers due to the sudden economic growth. Their going has been tough ever since the advent of the IT industry. It is impossible to find a solution to this problem. It is because this difference could not be met by the people unless the number of educated people in India increases.

It is high time that the Indian government takes necessary steps to improve the educational standards in the country. It is a serious issue and must be dealt with very soon because it is the survival of millions of Indians in question.

test

2008-02-12T10:15:00.001-08:00

According to recent studies, its been revealed that the influential antioxidant nutrients in tea plant which are known as flavonoids, aid in defending the body against a number of diseases. The regular intake of tea might help many body tissues, such as:
1. Liver: Tea apparently aids the liver’s function in removing toxins from the blood, including the removal of cancer causing compounds.
2. Brain: Tea might be involved in arousing the nerve cells to make more protein (apo-A) that may support in helping to postpone the beginning of dementia linked up to Alzheimer’s disease.
3. Weight: The use of green tea helps burn the calories by raising fat oxidation and heat production. The flavonoids in green tea are found to be helpful for doing so.
4. Heart & Blood vessels: The LDL cholesterol, commonly known as the bad cholesterol can be reduced by tea intake. It also helps in intensifying the capacity of the vessels to react to stress. Several studies have revealed that the consumption of tea has decreased the dangers of heart disease and stroke.
5. Bones & joints: Tea can help preserve the bone minerals density when growing older. It may also avert fractures and reduce osteoporosis.
6. Teeth: Tea consumption helps in fighting against the bacteria causing cavity and plaque.
7. Immune System: It is found in a recent study from Harvard that tea can assist in holding up a good immune system that can competently protect from infectious ailments.
8. Cancer: The tea flavonoids help in restraining the growth of premalignant lesions and cancers in various tissues, including intestine, pancreas, bladder, lung, breast, liver, skin, mouth.

Xobni

2007-09-29T07:00:00.001-07:00

Catastrophic Medical Insurance

2007-07-10T12:49:00.000-07:00

Catastrophic Medical Insurance

Written by: Ayesha Asghar
Dated: June 23, 2007

The catastrophic medical insurance plans are at times proposed to you when you don’t
intend to give out money for the areas that you don’t require. Also, you might need to go
for this insurance plan if you employer is not proposing or giving you any insurance plan.
This insurance plan comprises of lofty subtractions from your pay for health insurance
purposes but lesser supplementary charges per month. This plan requires you to pay from
your pocket for the trips made to a doctor and for the medicines that are advised by your
doctor in such cases. But other expenses like the one for hospital and other medical costs
are adjusted in the amount that is to be deducted from your pay. Mostly these medical
insurance plan pay for the lab test, you stay in the hospital, diagnosis process, x-rays,
surgery.

Generally the deducted amount in these insurance plans starts from $500 and then moves
on. Most of the people receive ‘caps’, which is a lofty benefit payment for lifetime. And
this amounts between $1 million to $ 3 million. If one reached a point where he obtains
cap then this policy would nullify for him. The costs that are associated with pregnancy
or maternity protections are not covered in the catastrophic medical insurance plans once
you’re in for a complete year after the date you joined.

If you select a plan with loft deductions then you would be anticipated to give out money
till the costs arrive at a point that of the deductions. It might be risky if you choose to
remove your covering in order to lessen your supplementary charges per month.
Normally people going for this insurance plan are in 20s or in the age ranges of 50 to 65
years. The young people go for it if they are not getting any covering for medical
purposes at work or if they are independent. Where as the adults choose this insurance
plan for the fear of any casualties related to finance resulting from a grave disease. They
are inclined to be in a healthy condition, with lesser medications and are worried about
the preserving of the supplementary charges and prefer to give out money from their
pocket every time they see a doctor.

Now let me give you few advices for the selection of a catastrophic health insurance plan.
Before hooking up for one, you need to review and think about few factors closely. Do
check out that how much are the supplementary charges are going to cost you monthly,
quarterly and yearly. You also need to keep in mind about the amount that is affordable
for you when it comes to pay for the deductions. You also need to focus that to which
extent is this covering comprehensive for you and how you want it to be. Then you need
to see if you required the medicines that are instructed to you by the doctor. Also you
need to check is if you will be able to give out money from your pocket for the trips made
to the doctor. In case you have any conditions you need to make them realize those. You
also need to see the frequency of your sickness. Lastly a check on the lifelong benefits
per year.

SMALL BUSINESS HEALTH INSURANCE

2007-07-10T12:34:00.000-07:00

SMALL BUSINESS HEALTH INSURANCE

Written by: Ayesha Asghar
Dated: June 23, 2007

It is practical to opt for small business health insurance so that one protects his employees
and also the business from all kind of situations resulting from a death, damage and
sickness.

Both the employee and employer are well aware of the benefits of the small business
heath insurance and take this supplemented restoration of confidence as a lucrative offer
with a job. The employer will see this as a payback or backup in case if he suffers any
loss and it will be a compensation for his lesser profits if his employee’s incompetence or
inability to work because of a brief break or permanent break from the work.

There are various packages or offers for this kind of insurance:

Protection of Income: There might be circumstances and situations faced by the
employees where they might not be able to work due to sickness or some damage. Then
this protection of income will come as a rescue, which would mean that they would still
receive the regular income whilst they are not working.

Private Medical Cover: This would require that the members of the staff are dealt with
and taken care of properly without any hassles and inconvenience, therefore reducing
interruption that would occur to your business and the staff member’s work. It would cost
much though.

Critical Illness insurance: This insurance can be merged with the life insurance and can
also be given singly. This kind of insurance protects the employees in critical situations
where they might be identified with a grave disease like cancer. This will come up as an
expensive one and also huge obligation for the employer.

Life Insurance: This type of insurance is supposed to protect the employer if he faces a
situation that of an employee’s death. This gives an inclusive total or a normal amount
and this would be regarded at a rational rate keeping in mind the possible product value.
This insurance can also be altered in order to compensate for the situation like that of
demise of a business partner or an important share holder. Then this will protect both of
the employee and the business with inclusive totals correspondent to the share value. This
gives the other shareholders and the partners and also permits them to purchase the share
if the family of the deceased person is not planning to work any more.
Employer’s Liability Insurance: It is important to note down here that these business
insurances for health causes are highly practical choices but by no means are essential. If
some one from your close family is working for you, then you don’t need to have any
insurance, but in case of any outside you would need to. Also when there is only one
employee who might be the owner of the half of the shares of the business, then this
insurance is not required.

The insurance for employer’s liability protects the business from any kind of fees that is
related to law, or payments for making up that are required to be given to the staff
members as an outcome of some harm that might have happened due to your company.
Key Man Insurance: There might be situations where you will find some of the staff
members as pivotal for your business and so that you would be quite dependent on them.
This type of insurance takes care of such an occurrence where you might be deprived of
these people due to sickness, demise or maybe some grave disease.

AFFORDABLE INDIVIDUAL HEALTH INSURANCE

2007-07-10T12:30:00.000-07:00

AFFORDABLE INDIVIDUAL HEALTH INSURANCE

Written by: Ayesha Asghar
Dated: June 23, 2007

Here in this article we guide you to selecting an affordable individual health insurance
plan. Normally the PPO plan is the one that you might find moderate and which could be
adjusted easily in your financial plans. Where, PPO stands for the Preferred Provider
Organization.

Next you need to take care of the deductions that are supposed to be made from your pay.
Now these depend on the location you live and the offers that are available for that place.
In general case, you will face two situations for this. Either you go for single protection
or for a one that is for your entire family. Here the individual one might cost you around
minimum of $500 and maximum would be $5,000. If you select the family protection, for
that the minimum costs would be $1,500 and might go up to $10, 000. Now these
deductions are also dependent on the facts that are the providers of this insurance plan
fall under participating category or non-participating one. You need to check out for that
for the location you live in.

Now the next thing that you need to ponder on is that if you select a protection for your
family, then are the deductions going to be made distinctly for the individuals or not.
Mostly the deductions are made on individuals, which means separately. These would
sum up to the amount that would be equal to that of twice of thrice of an individual. So if
you have a family of greater than four members that is protected under this plan, then
only two or three individual would face the deductions and the rest won’t be.

When an individual faces a deduction, then according to this plan you will be given out
money for a fraction for the protected expenditures made for the medical purposes as they
would have specified in their specifications sheet. Now these fractions are subject to
change and are dependent on the locations and the offering of that particular location.
In this plan, for some services are made by the company upon the receipt of the medical
care or any medical instructions. There are aids offered such as getting paid for the trips
made to the doctor or any sickness. For that you need to check out on the details of copayments
that are offered. And so the insurance plan would be protecting you from the
other costs.

You may see some advantages of these co-payments but these do not protect you from
the deductions. They might not help in lessening up in these subtractions from your
pocket.

Now the limits that are set on the yearly payments are separate for the providers that
might be non-participating or maybe participating. If you attain the status of the provider
who is sharing then this insurance plan would be protecting the offering cent percent. But
then here the co-payments can not be counted neither any other cost can be included
when it comes to the limitations per year.

If you are going to take medicines from the sharing locations where instructed medication
is sold, then you might get a discount. And in case you obtain an Rx deduction status then
you will be protected for medications via co-payments.

Often one need to check for the costs related to dental purposes. If it’s not a case of some
damage then you might not get the benefit for dental costs.

Tignanello handbags

2007-07-03T12:14:00.000-07:00

Title: Tignanello-All you wanted to know about Tignanello brand of handbags

Description: The brand Tignanello produces high quality leather handbags, wallets, and other accessories. The leather goods are an financially manageable items of luxury, uniting use with trend.

Handbags have been used through ages. It was in 1988 that Tignanello was found and to date it has proven to be a topper in the handbags made of leather. Tignanello focuses on three factors while manufacturing its products – usage, quality and skillfulness and function. The Tignanello uses the materials of very superior quality to produce sumptuous leathers a high referred in their creations.

Quality of Tignanello handbags

The manufacturers of Tignanello handbags use leather that is very smooth and is not artificial. This natural material is converted to leather using dying with real resources that makes it better of. Reliability and effectives for a long period of time are two major factors kept in mind when these handbags are produced. The Tignanello handbags are stitched in a strong manner and buckles attached to them are very strong as well. The zipping used in these handbags is flawless. These are designed keeping in mind the requirements of the women. The Tignanello handbags thus are useful and reasonable whether you buy them for office use, a trip or a party.

Prominent Tignanello Handbags

Tignanello Huntington

This bag is made from leather of that is very fine in nature and is stoned to give a pebblish look. The shade it comes in is that of brown of a nut. The embellishments on it give it a traditional look. This bag has two zips which makes its easier to open and use.

Tignanello Newport Tote

This handbag is too made of the leather of very superior quality that has been pebbled and has been stitched in matching. This tote has two handles that are moveable and so can be easily adjusted. The tote has been outlined in a very lovely manner. The leather grain that has been pebbled is nicely coordinated with hardware in shade of silver that accents the handbag. There is an inner pocket with zip, which offers good capacity to hide your stuff.

Tignanello Catalina

This Tignanello handbag is available in various eye catching shades like camel, claret, mustard, nut brown and navy. The leather used to produce it is very fine and smooth. The handbag is stitched with a matching white shade signature. It has two handles and its easier to be carried by shoulder. The hardware of silver illuminates the traditional shape with a slight glow.

Buying guide of Tignanello handbags

The brand Tignanello had opened up several stores in various cities and is available in major department stores and fine specialty stores across the country or at their website through our partnership with eBags. . The real Tignanello handbags can be found here. In order to avoid any deceit of buying some replica Tignanello handbags, you are advised to shop from the outlets owned by Tignanello. There are several online stores that offer discounts and reductions for Tignanello handbags and other products. The replica Tignanello handbags are also up for grabs at very low prices but then these are not dependable. Also you will find these replica Tignanello handbags to be of very low quality and poorly made. The company is taking steps to thwart the production of these replicas and very soon they might get rid off it too.

tod's handbags

2007-07-03T11:36:00.001-07:00

Title: Tod’s-All you wanted to know about Tod’s brand of handbags

Description: The brand Tod’s is owned by an Italian company. The Tod’s group manufactures shoes and leather products. Diego Della Valle is the president of the company. Tod’s is well known for the shoes it produces for drivers and its D-bags.

Handbags have been in use for ages now. It was in 1970 when Tod’s was started. Filipo Della Valle set up a small business. Initially he was in the production for shoes. Later it was his grandson, Diego who expanded the business and added products like handbags, gloves and belts to the production line. Later on he also introduced new brands under his company and named them Hogan and FAY.

Quality of Tod’s handbags

Tod’s is highly regarded for its superior quality goods. The exceptionally good quality has been a major reason to add to its credibility and good name to the company. The handbags are a fusion of eye catching designs and sophisticated outlook. At present, Tod’s is offering many goods in its collection because of the quality it maintains. The speciality of Tod’s products is the result of the adroit artists and the respect it has gained over generations. A number of celebrities today fall for Tod’s collection.

Prominent Tod’s handbags

Tod's Charlotte Lavoro Grande

This is an expensive and magnificent tote by Tod’s. It has a strap that can be easily adjusted. This tote also has two handles that are moveable and have a silver polish on hardware. You wear it by strap or carry it by the handles, you are bound to look gorgeous carrying it and you yourself will also love it. This tote also has small pockets in shape of halfed circles on both the sides. This tote is large in size and has a capacity to be itemized nicely.

Tod's Charlotte Piccola

This is a lovely handbag. It’s both elegant and fashionable. For all the sport lovers, this handbag has been gracefully fashioned to have a sporty look. The leather that has been used for it is pebbled and very soft. This Tod’s handbag has been stitched to give a resemblance of something styled and design as of saddle. Due to the high quality leather used for it, this Tod’s handbag is very reliable. It also has two pockets on both the side that are in shape of circle halves. It has all that can be tagged as entirely new and fresh.

Tod's D Bag

This Tod’s handbag is both expensive and trendy and as a tribute to Princess Diana, the ‘D’ in its name signifies it dedication and tribute to her. This handbag is a top seller very happening at the moment. It is produced using luxurious leather and is strongly manufactures in accordance with the tradition of Tod’s handbags. It has two handles which are moveable. The way it has been stitched gives it a rich look. Amazingly designed handles also have hanging charms and one of them reads out to be ‘D-Bag’. It’s a must to have handbag by Tod’s.

Buying guide of Tod’s Handbags

The brand Tod’s has opened up several stores in USA, Asia and Europe. There are also featured stores in Tokyo and New york. The original Tod’s handbags and Tod’s products can be found here. In order to avoid any deceit of buying some replica Tod’s handbags, you are advised to shop from the outlets owned by Tod’s. There are several online stores that offer discounts and reductions for Tod’s handbags and other products. The replica Tod’s handbags are also up for grabs at very low prices but then these are not dependable. Also you will find these replica Tod’s handbags to be of very low quality and poorly made.

furla handbags

2007-07-03T11:34:00.001-07:00

Title: Furla-All you wanted to know about Furla brand of handbags

The brand that originated from Italy is today quite popular for its handbags among women. Other than its outlets in Italy, it is also distributing its products to several countries like USA, Europe etc.

The handbags are in great demand and use through ages. It was in 1927, when ‘Furla’ was established in Bologna, Italy. The company has its main office in Villa Bellaria, which is a classical building from the 18^th century. Aldo Furlanetto was the one to start it and later his kids kept the business going. They made major changes in the styling, manufacturing and the way for distributing it outside Italy. They introduced new range of expensive products such as hats, gloves, sun glasses, jewellery, handbags and scarves. In recent times they have also added up shoes to their collection. But it’s the handbags that make this brand known.

Quality of Furla handbags

This brand that hails from Italy has been recognized for its products that are designed with a gracefulness and effeminacy. The Furla handbags are up for grabs in a variety of sizes. These are produced from leather that is of high quality. You can find them in several colours and designs.

Prominent Furla handbags

Furla Arina Hobo Handbag

These hobos are available in sizes categorized into medium, large and extra large. One can easily select the hobo that suits the needs. This Furla hobo is made from suede or leather. It is known for the colors it is available in and has an excellent making. The hobos of medium and large sized are designed such as they give a look as if covered with small stones/pebbles and comes in easy going shades of honey, coffee and black & white. The original leather of calf is used for them. The extra large sized hobos are created from leather with an outlook of pebbles and the front is covered by the suede that is smooth to touch. The hobos are embellished using the hardware made of silver and gold. The hobos consist of sturdy handles or straps that are hung over shoulders. The top closure if zipped, there is an inner zip present as well, pocket for the mobile phone and a sumptuous outlook.

Furla Brera Extra Large Shopper in Ostrich

This bag comes in extra large size and is not only spacious but also trendy. The design and shape are nice and eye catching. Furla improvises the traditional gracefulness and modern fashion. This tote has a flap at the top and a closing made of silver. The straps can be easily adjusted. The elusive hardware made of silver is used to beautify it. It has an interior pocket with a zip and a pocket for mobile phone as well. You can easily find it in soothing colors like of honey and jade.

Buying guide for Furla handbags

The Furla brands possess has it outlets located in Italy and these are imported to USA and several other countries. These can be also found in top stores. The point of great importance here is to keep away from the replica Furla handbags that are flowing out there in the market. To avoid the misfortune of purchasing a replica, you should be well aware of the facts that distinguish the original ones from the replicas. So the best place from where they can be bought is the brand stores. There are several stores on the internet as well that offer discounts for the authentic Furla handbags, you can purchase them online as well.

dooney & bourke handbags

2007-07-03T11:30:00.001-07:00

Dooney & Bourke-All you wanted to know about Dooney & Bourke brand of handbags

The brand ‘Dooney & Bourke’ was established in 1975. Today, Emma Roberts represents the company. She is also the niece of the famous actress, Julia Roberts. The main store for this brand is located in the New York. Dooney & Bourke owns 150 stores with-in the country today.

The usage of handbags has been witnessed since distant past. It was in 1975 when Peter Dooney & Frederic Bourke started this brand and set up it in South Norwalk, Connecticut. At present the brand is famous for its handbags that are decorated with distinctive charms made of leather and silver. The brand is also known for its purses that are made from fabric and has the initials D&B in a unique manner. These alphabets of the D&B initials have been created in eye catching colors. The brand is also known for the totes, wallets, hats for women and the pet straps it manufacturers.

Quality of Dooney & Bourke Handbags

The D&B handbags and purses are available in several designs, namely satchels, bowler bags, barrel bags and duffle. The bags have been designed to be smooth and glossy, giving them a sexy look in tones of black and then to beautify, traditional buckles of gold are used.

Prominent Dooney &Bourke handbags

Dooney & Bourke's Bucket Bag

This is the top seller of D&B and is priced around $140. The cute bubblegum color that this bag has been given attracts you more towards it. D&B offers a smart fusion of traditional bucket designed bag with logos that are printed thus giving an impression as if dusted and the zipped handle is designed into heart shaped in pink color. This traditional bag gives a good capacity for keeping things inside, a pocket for the mobile phone and is lined with a very thin and cheeky silk. Its available in several colors, all of them are awesome.

Dooney & Bourke Large Safari leather hobo

This is big sized hobo made up of leather and is printed with zebra design on it. It is priced around $395 and is available in black color. It comes with buckles on the both sides that can be easily adjusted. It has a raised one-click closing. There are pockets in the inner side with zip. The dimensions are 18’’, 15’’ and 10’’.

Buying guide of Dooney & Bourke handbags

The D&B has opened up around 150 stores in various cities in the USA. The original Dooney & Bourke handbags are easily found here. In order to avoid the mishap of buying some replica Dooney & Bourke handbags, you should prefer to purchase from the brand owned outlets. There are several online stores that offer discounts and reductions for D&B handbags and other products. The replica D&B handbags are also up for grabs at very low prices but then these are not dependable.

beijo handbags

2007-07-03T11:27:00.001-07:00

Beijo-All you wanted to know about Beijo brand of handbags

The owner of Beijo operates in Florida and presently the Beijo Handbags are up for grabs in the East Coast of U.S.A and Europe.

Handbags came into use in distant past. It was the efforts of Susan Handley that created this brand and named is ‘Beijo’. For those who do not understand Portuguese, ‘Beijo’ is a word from Portuguese and refers to ‘kiss’. It was in 2001 when Susan established this brand in Florida. Being a single parent she started this business from her home. The brand is gaining popularity day by day. Susan personally promotes these brands at the parties and to her friends. Because of no budget to spare for the marketing purposes, word of mouth is playing a major role in the popularity of this brand. Susan is very much interested in the development of society, health issues related to women, providing support to kids and help for education purposes and so she aims to contribute a fraction of money that results from the sale of Beijo products.

Quality of Beijo Handbags
Beijo specializes in the production of purses, handbags and wallets. These are some of its famous and well-liked products. The reason which makes Beijo products different and yet likeable includes the thin thread-like material that is used for its production. You can easily remove dirt from this type of material, which makes its special. The Beijo handbags, Beijo purses and Beijo wallets are designed in accordance with the changing trends in fashion and the requirements of the people. No wonder why everyone longs for Beijo products.

Prominent Beijo Handbags

Metallic Neutrals
This range has gained wide spread popularity and all credit goes to the eye-catching shades in shimmer that are changing trends.

"O" Ring Collection
This collection is also very popular among women and girls. What makes it special is the ‘O’ shaped rings on these bags and to add more, every Beijo Handbag under this collection has a different shape. This ring is made up from silver which has a sheen that is hard to let go off. The range of prices for this ring collection is from $40-$125.

Fall Classic Buckle Collection
The promiment handbags under this collection consist of a buckle made from silver. These handbags come in traditional forms, are designed according to the latest trends and the signature on the silver buckle makes it unique. These are available in wide range of colors, ranging from light soothing colors to the bright and lively tones.

Buying guide for Beijo handbags
We advise you to shop from the outlets owned by Beijo. This is a safe way to get the original bags. The shops are flooded with the replica Beijo Handbags and one should be aware of this. The presence of Beijo stores solves this problem of replicas. You might find the replica Beijo handbags quite close to the real ones in the outlook but these are not dependable. Also these would be cheaper in price and this factor might attract you to them but then this would not be long lasting.

BCBG bags 2

2007-07-03T11:23:00.000-07:00

Title: BCBG-All you wanted to know about BCBG brand of handbags

Description: BCBG Max Arzia, as it is called established in 1989. Nearly for the past two decades it has gotten the fashion industry head over heels. The brand has a great collection for women and possesses around 100 stores. These stores are located in South America, Asia, Europe and North America.

Handbags have been in use for ages now. In 1989, Max Azria added another fashion house to the industry, called BCBG. Where Max not only is the owner but also designs for the brand. Max’s hard work has made BCBG carve a niche for itself and is one of the famous and main brands for which women long for.

Quality of BCBG handbags

BCBG handbags offers all those special features and attributes that makes women go gaga over them. Ask any woman and she will be more than happy to grab a handbag designed by BCBG. The features that make it different and unique are the design that is created according to the traditions and mannerism that complements the West. The BCBG handbags and BCBG wallets are always in demand because of their way of styling that is always totally new and for current prices. Max Azria designs the women’s range of handbags and purses. At the end of every season, customers are given good discount offers which are quite manageable. The fascinating colors, notable palettes and high quality of material are used to produce them. All these features combine to make the BCBG handbags special and exclusive.

Prominent BCBG handbags

BCBG Roma Purses

This range of BCBG purses are created from artificial leather and are small in size. The purse consists of one-click closing at the top, a pocket at the front which is zipped and a pocket with zip in the inner side.

BCBG Soho Handbags

These are produced of thick cotton fabric with velvety ribs and are an excellent range. It has a large sized clasp, a pocket to carry mobile phone and a pocket at the inner side with a zip.

BCBG Bleecker Hobo

This is an adorable range that comprises of clasp that is pliable, inner pocket with a zip, a small pocket at outside that drops out, stud made of big brass are used to beautify it, and the inner side is completely lined with a fabric and has a zipped opening.

Buying Guide of BCBG bags

The BCBG brands possess around 100 stores that are located in areas such as South and North America, Asia and Europe. The BCBG also has placed it bags for sales in various top stores. What is the point of importance here is to keep away from the replica BCBG handbags that are flowing out there in the market. To avoid the deceit you should be well aware of the facts that distinguish the real ones from the replicas. So the best place from where they can be bought is the brand stores. There are several stores on the internet as well that offer discounts for the authentic BCBG handbags, you can purchase them online as well.

BCBG handbags

2007-07-03T11:08:00.000-07:00

Title: BCBG-All you wanted to know about BCBG brand of handbags

Description: BCBG Max Arzia, as it is called established in 1989. Nearly for the past two decades it has gotten the fashion industry head over heels. The brand has a great collection for women and possesses around 100 stores. These stores are located in South America, Asia, Europe and North America.

Handbags have been in use for ages now. In 1989, Max Azria added another fashion house to the industry, called BCBG. Where Max not only is the owner but also designs for the brand. Max’s hard work has made BCBG carve a niche for itself and is one of the famous and main brands for which women long for.

Quality of BCBG handbags
BCBG handbags offers all those special features and attributes that makes women go gaga over them. Ask any woman and she will be more than happy to grab a handbag designed by BCBG. The features that make it different and unique are the design that is created according to the traditions and mannerism that complements the West. The BCBG handbags and BCBG wallets are always in demand because of their way of styling that is always totally new and for current prices. Max Azria designs the women’s range of handbags and purses. At the end of every season, customers are given good discount offers which are quite manageable. The fascinating colors, notable palettes and high quality of material are used to produce them. All these features combine to make the BCBG handbags special and exclusive.

Prominent BCBG handbags
BCBG Roma Purses
This range of BCBG purses are created from artificial leather and are small in size. The purse consists of one-click closing at the top, a pocket at the front which is zipped and a pocket with zip in the inner side.

BCBG Soho Handbags
These are produced of thick cotton fabric with velvety ribs and are an excellent range. It has a large sized clasp, a pocket to carry mobile phone and a pocket at the inner side with a zip.

BCBG Bleecker Hobo
This is an adorable range that comprises of clasp that is pliable, inner pocket with a zip, a small pocket at outside that drops out, stud made of big brass are used to beautify it, and the inner side is completely lined with a fabric and has a zipped opening.

Buying Guide of BCBG bags
The BCBG brands possess around 100 stores that are located in areas such as South and North America, Asia and Europe. The BCBG also has placed it bags for sales in various top stores. What is the point of importance here is to keep away from the replica BCBG handbags that are flowing out there in the market. To avoid the deceit you should be well aware of the facts that distinguish the original ones from the replicas. So the best place from where they can be bought is the brand stores. There are several stores on the internet as well that offer discounts for the authentic BCBG handbags, you can purchase them online as well.

Bally handbags

2007-07-03T10:45:00.001-07:00

Title: Bally-All you wanted to know about Bally brand of handbags

Description: The brand ‘Bally’ is today owned by the Texas Pacific Group that happens to be an American investment fund. Today Italy and Caslano are the two cities that are its centre of operation.

Handbags came into use in distant past. The brand ‘Bally’ was found in 1851, when Carl Franz Bally and his brother set up a new company and named it ‘Bally & Co’.
The companies faced many difficulties through the century. And then it had no option but to sell the brand in 1999 and today it is owned by Texas Pacific Group. Initially this brand focussed on the production of shoes only. It was later in 1976, when they introduced a new range of products like handbags and clothes and several other products made of leather. Today, ‘Bally’ is one of the top brands that manufacture goods and accessories made of leather.

Quality of Bally Handbags
The brand ‘Bally’ is known for the production of goods made up of leather such as apparel, accessories, shoes and more. The brand mainly focuses on the purses, handbags and wallets. The leather used to create the Bally handbags, Bally wallets and Bally purses not only excels in the quality but is also smooth and pleasant to touch. Bally bags offer a great deal of security for your stuff by adding both inner and outer pockets with zips. The brand also adds metal rings of gold to embellish the Bally handbags.

Prominent Bally hand bags

Bally Mimosa tote
This is a large made containing long strap and is hung over the shoulder. It is made up of leather. The embellishments on it are made in the colors of gold. It consists of two straps. The inner side of the purse has been nicely lined along with a zip in its center. This bag has a capacity to hold stuff such as bottles, books, wallets etc.

Bally Maybelle Shoulder Bag
This impeccable and firm bag, as the name suggests is made to be hung over shoulder. It is made up of leather. This Bally bag has just one strap and one click closing made of magnet. It also has a pocket with a zip and another pocket which is made to keep you mobile phone in it.

Bally Cassise Hobo
This is a pretty bag with a long strap that is hung over the shoulder. It is made of fine quality leather that is smooth to touch. The bag has been made to having two straps, an outer pocket at front with a flap and raised at bottom. The measurements in length, width and height are 12’’, 3’’ and 9’’ respectively.

Buying guide of Bally handbags
The brand Bally had opened up several stores in various cities. The original Bally handbags, Bally purses and other Bally products can be found here. In order to avoid any deceit of buying some replica Bally handbags, you are advised to shop from the outlets owned by Bally. There are several online stores that offer discounts and reductions for Bally handbags and other products. The replica Bally handbags are also up for grabs at very low prices but then these are not dependable. Also you will find these replica Bally handbags to be of very low quality and poorly made. The company is taking steps to thwart the production of these replicas and very soon they might get rid off it too.

baenciaga handbags

2007-07-03T10:41:00.000-07:00

Balenciaga-All you wanted to know about Balenciaga brand of handbags

Today the Gucci Group owns the brand ‘Balenciaga’. It is presently running two shops in USA, one of which is in New York and operates as their centre of operations. Recently they also happened to open one outlet and Bangkok. Their next step is to set up another one in Boston.

In distant past, the usage of handbags shot up. It was in 1918 when a fashion designer, Cristobal Balenciaga Eisaguirre, from Spain set up a fashion house. It was due to the great adoration in his locality that he further planned to set up another shop in Madrid. His next step was in 1937 Barcelona. And so the fame continued. And all the fashion houses are addressed to be “The House of Balenciaga”.

Quality of Balenciaga Handbags
Today this brand happens to be one main and famous fashion brands. It is known for producing handbags and wallets for women that are superior in quality. Today the Balenciaga handbags, Balenciaga purses and Balenciaga wallets happen to be the most wanted due to the way it is nicely structured and are carried by the females around the globe. The features incorporated consists of lastingness, well-made, outlook that is matchless, designed pertaining to traditions and are of superior quality. Queen of Spain and Belgium happen to be a big fan of Balenciaga purses and wallets.

Prominent Balenciaga Handbags

Balenciaga Motorcycle Designer Handbags
These bags have been designed nicely and consist of fringes made up of leather, there is a strap left to one’s choice, pockets both outside and inside, make up mirrors that are nicely matched and stud are used to add to its beauty.
Balenciaga Twiggy Handbags
These handbags are created from leather that is of very high quality. It consists of a strap that is to be hung over the shoulder and can be removed too if wanted. There is a pocket outside with a zip, embellished with stud and closing to the handbag is zipped.
Balenciaga Whistle Handbags
This handbag is produced from leather. To grip from hands it offers two handles, zipped closing, internal pocket with zip, click closing of magnet and beautified exterior with charms of penny symbols.

Buying guide of Balenciaga Handbags
You can find the Balenciaga bangs around the world in famous stores. The bangs can be categorized in to Balenciaga Cheap Replica handbags and Fine quality Replica Balenciaga handbags. Several copies of these handbags are being offered in various places but these are not even close to the ones offered by Balenciaga. These replicas are poorly made and are of quality that is not up to standard. You will find that these copied bags are not long lasting as well. The best option is to get Balenciaga handbags from the brand’s outlets so that you are assured to get an original one. There are several shops on the internet that too sale authentic stuff and give discounts as well.

Isabella fiore handbags

2007-07-03T09:56:00.000-07:00

Title: Isabella Fiore-All you wanted to know about Isabella Fiore brand of handbags

Description: The brand ‘Isabella Fiore’ is today owned by the two friends from Los Angeles. Today there handbags are available with America’s chain of luxury departments like Nordstrom, Nieman Marcus, Saks Fifth Avenue, Bergdorf Goodman etc.

Handbags have been in use since distant past. In 1996, there was made an addition to the fashion industry when ‘Isabella Fiore’ entered the industry. As you might be deceived by the name and have an impression of an Italian designer might be after this but that’s not the case. ‘Isabella Fiore’ is from Italian and refers to ‘beautiful flower’. This brand is owned by two friends, namely; Tranh Huynh and Jennifer Tash. Both are based in Los Angeles. Their collection includes remarkable handbags, purses, shoes, wallets and luggage products. Celebrities like Madonna, Kate Hudson and Katie Holmes often carry stuff of this brand.

Quality of Isabella Fiore handbags
The handbags offered by Isabella Fiore leave an instantaneous influence on you. You will find them designed to be very beautifully and lively. They come with embellishments of all kinds including straps woven together, showy tassels, metallic studs and tempting shades. Isabella Fiore handbags are created in accordance with the latest fashion and trends. They offer a large range and variety to be selected from.

Prominent Isabella Fiore handbags
Metal of Honor Ingrid Messenger
This Isabella Fiore creation is unique in its kind. It has been created two types of leather from Italy. One of them has been covered with pearls. The upper layer has been put on top the bottom one in such a manner that seemed to be diced. This adds to an outlook pertaining to dimensions. It is available in rich brown shade, with studs put over in classis manner and decorated with tassels.

Whip Flash Alexia Large Hobo
This hobo is available in brownish red that is vivid in color and large in size. The bag has been beautifully studded that makes it outstanding in its design. It has more capacity to offer. It has been stitched with rod and has a large buckle. A handy handbag to have.

Whip Flash Audra Medium Hobo
This hobo has been given a stitching of rod like. And this has been a factor of choosing their names. Many celebrities have been seen carrying this hobo, one of them being Katie Holmes. This hobo give plenty of space to you to put in your stuff. It has been beautified with tassels on the outside, studded in classic fashion, stout buckles and very showy in outlook.

Buying guide of Isabella Fiore handbags
The brand Isabella Fiore is available with America’s chain of luxury departments like Nordstrom, Nieman Marcus, Saks Fifth Avenue, and Bergdorf Goodman etc. The real Isabella Fiore handbags and other products can be found here. In order to avoid any deceit of buying some replica Isabella Fiore handbags, you are advised to shop from the above mentioned outlets. There are several online stores that offer discounts and reductions for Isabella Fiore handbags and other products. The replica Isabella Fiore handbags are also up for grabs at very low prices but then these are not dependable. Also you will find these replica Isabella Fiore handbags to be of very low quality and poorly made. The company is taking steps to thwart the production of these replicas and very soon they might get rid off it too.