This is the first article on database indexingCopy the code

B tree

Directory:

  1. What is a B tree
  2. The minimum degree of a B tree
  3. B tree height
  4. When do you use B trees
  5. B tree insertion
  6. Delete the B tree

Body:

  1. What is a B tree

    1> is a balanced search tree. 2> Is designed for secondary storage devices like disks or other direct storage. 3> Is similar to a red-black tree. 4> Nodes can be divided into internal nodes (non-leaf nodes) and leaf nodes. 5> Nodes can have more than one keyword. 6> Assume that the number of keywords in a node is N, then the number of children in the node must be N +1 < 60) 8> Assume that the number of keywords of node X is N, and from left to right are x1,x2... Xn (as shown in figure n=2,x1=50,x2=60) according to article 6>, the number of children is n+1, from left to right are C1, C2... Cn + 1 (the following figure c1 = (35 or 40), c2 = 55, c3 = 70), then the sort rules must be c1 < x1 "c2" x2 <.. Xn <cn+1 9> Each leaf node must have the same depth, that is, the height of the tree is consistent. 10> The number of keywords per node has an upper limit and a lower limit, depending on the minimum degree t set by the tree. T-1 <= n <= 2T-1 The root node is not restricted by the minimum T-1. If the tree is non-empty, the root node has at least one keywordCopy the code

A typical B tree is shown below

B. The minimum degree of the tree 

1> The number of keywords on each node has an upper limit and a lower limit, depending on the minimum degree t set by the tree. T-1 <= n <= 2t-1 root node is not restricted by the minimum T-1. If the tree is not empty, the root node has at least 1 keyword. 2> When a node has exactly 2T-1 keywords, the node is full (this concept is used when inserting b-tree). Then the node is minimal (this concept is used when deleting a B-tree)Copy the code

B. The height of the tree

Why do we care about the height of the B-tree? Because the b-tree is designed primarily for disk access, and the height of the B-tree is proportional to the number of disk accesses.

Because the minimum number of keywords on the root node is 1 and the minimum number of keywords on other nodes is T-1, the number of keywords on the tree n meets the following requirements:

4. When are B-trees used

As described in section 1, B-trees are designed for disks or other secondary storage devices with direct storage. A typical b-tree usage scenario is a database.Copy the code

As can be seen from the height formula of the tree, the larger t is, the more keywords in the node, the smaller the height of the tree, and the fewer disk access times.

The more node keywords there are in the tree, how many are appropriate?

In fact, the keyword in a node is the size to be read by the disk at a time. The disk usually loads one or more pages at a time, and the size of a page ranges from 4K to 8K

So the keyword is less, a disk read, will cause waste; Too many keywords, a disk read read.

So it’s important to set the right t value. In addition, during dynamic insertion and deletion, ensure that the B-tree complies with the above features of the B-tree to meet the requirements of application scenarios.

Insertion and deletion of B-trees will be discussed in the next chapter.

Finally, learning b-trees can also help us understand database design


Other relevant chaptersCopy the code

B tree, no mystery, no mystery, no mystery, no mystery, no mystery, no mystery, no mystery, no mystery, no mystery, no mystery, no mystery How to Find and Replace Inappropriate indexes