background

First, let’s talk about B trees. Why use B trees? We need to understand two facts:

【 Fact 1】

The speed of access varies greatly with different storage capacities. For example, the disk access time is about Ms, and the memory access time is about NS. An analogy is that if a memory access takes 1 second, an external memory access takes 1 day. Therefore, the current storage system is hierarchical organization.

The most commonly used data is stored as much as possible in higher, smaller storage, and is only sought in lower, larger storage if it cannot be found in the current tier. This explains why, when dealing with large amounts of data (i.e., not being able to store the data in memory at once), the actual running time of the algorithm often depends on the number of I/OS between different storage levels. Therefore, the key to speed up is to reduce IO.

【 Fact 2】

Disk data is read in blocks (or pages). All data in the same data block can be read at one time.

In other words, reading 1B from disk is almost as fast as reading 1KB! Therefore, if you want to increase speed, you should take advantage of the bulk access feature of external memory, also known as disk preread in some articles. The system is designed this way based on a well-known principle of locality:

When a piece of data is used, the data in its vicinity is usually used immediately, and the data needed during the running of the program is usually concentrated

B tree

Suppose there are 1 billion records (100010001000), and if you use Balanced Binary Search Tree (BBST), the worst case lookup requires log(2, 10^9) = 30 I/O operations, Only one keyword can be read at a time (i.e. if the keyword is not the one I am looking for, I/O will have to be read again). Now, what happens if I switch to B trees?

B tree is a multi-fork balanced search tree designed for disks or other secondary storage devices. ** Multi-level storage systems use B tree to greatly reduce I/O times for external search. B tree can make full use of the efficient support of external memory for batch access and turn this feature into an advantage. ** At each level, a set of keywords is read from disk, in units of supernodes (that is, a node containing multiple keywords). So, how big is a group?

The amount of data stored on a node depends on the size of data blocks on the disk. For example, if the size of one block in the disk is 1024KB and the size of each keyword is 4 Bytes, you can set the size of each keyword group to 1024KB / 4 bytes = 256. At present, most database systems use m = 200~300. If m = 256, then the height of the tree storing 100 million data is approximately log(256, 10^9) = 4, that is, the number of I/ OS required for a single query is no more than 4, which greatly reduces the number of I/ OS.

Generally speaking, the root node of a B-tree resides in memory. The search process of a B-tree is as follows: First, because a node contains multiple (for example, 256) key codes, the search is conducted in order/binary first. If the search is found, the search succeeds. If that fails, the next level of node data is read from disk based on the corresponding reference (this involves a disk I/O), and the same sequence is searched within the node, and so on… In fact, a significant portion of the time spent looking up B trees is spent on I/O, so it is important to reduce the number of I/ OS.

Definition of B tree

B tree is a balanced multi-way search tree, the so-called M – order B tree, namely m – way balanced search tree. According to Wikipedia, an m-order B-tree must meet the following requirements:

  • Each node contains at most m branch nodes (m>=2).

  • Except for the root node, each non-leaf node contains at least chrysene M /2 gp branches.

  • If the root is not a leaf, there are at least two children.

  • A non-leaf node with K children contains k-1 keywords. (The keywords in each node are arranged in ascending order)

  • All the leaf nodes appear in the same layer. These nodes don’t actually exist, so you can think of them as external nodes.

The node can also be called a (chrysene M /2 gp, M) tree according to the upper and lower limits of its branches. For example, with order m=4, such a B tree could also be called a (2,4) tree. (in fact, the (2,4) tree is a special b-tree that has a special connection to the red-black tree! We’ll talk about red-black trees later.)

Moreover, the key of each internal node is used as the delimiter value of its subtree. For example, if a node has two keywords (let’s say A1 and A2), that means it has three subtrees. Then, the keywords of the leftmost subtree are all less than A1; The keywords of the middle subtree are between A1 and A2. The keywords of the rightmost subtree are all greater than A2.

For example, a b-tree of order 3 looks like this:

B tree height (understanding)

Suppose a B-tree is non-empty, has N keywords, height h (let the root be the first layer), and order M, then what are the maximum height and minimum height of the b-tree?

Maximum height

When the height of the tree is maximum, each node should contain as few key words as possible. By definition, the root node has at least 2 children (1 keyword), except the root node with at least chrysene m/2 gp children (chrysene M /2 gp -1 keyword), for the convenience of description, p = chrysene M /2 gp.

  • Layer 1 node (including 1 keyword)

  • Layer 2:2 nodes (including 2*(P-1) keywords)

  • Layer 3 2p node (including 2p*(p-1)^2 key)

  • …

  • H layer 2p to the h minus 2

So the total number of nodes, n

P + 1 (p – 1) * [2 + 2 p + p ^ 2 +… + 2 p ^ 2 (h – 2)] p p ^ 2 (h – 1) – 1

H ≤ log_p[(n+1)/2] +1 (p= chrysene m/2 gp)

The minimum height

When the height of the tree is the lowest, the keyword of each node contains at most m children (that is, M-1 keyword), then

N ≤ (m-1)*(1 + m + m^2 +... + m^(h-1)) = m^h - 1

H ≥ log_m(n+1) (where m is the base)

B + tree

B+ tree definition

B+ tree is a variant of B tree. The biggest difference between B+ tree and B tree is:

  • Leaf nodes contain all keywords and Pointers to corresponding records, and the keywords in leaf nodes are arranged in order of size, and adjacent leaf nodes are connected by Pointers.

  • A nonleaf node stores only the maximum (or minimum) keyword of its subtree and can be considered an index.

An example of a level 3 B+ tree :(feel the difference between a B tree and a B tree, the keywords are the same)

Q: Why are B+ trees better than B trees for file and database indexes in practical operating systems?

A:

  • B+ trees are better suited for external storage. Since internal nodes do not store real data (they only store the maximum or minimum keywords of their subtrees as indexes), one node can store more keywords, and each node can be indexed in a larger and more accurate range. This also means that the amount of disk I/O information in a B+ tree is larger than that in a B tree, and the number of I/ OS is relatively reduced.

  • MySQL is a relational database, interval access is a common situation, B+ leaf node added chain pointer, strengthen the interval access, can be used in the interval query scenario; Interval lookups are not possible with B trees.

Write in the last

Welcome to pay attention to my public number [calm as code], massive Java related articles, learning materials will be updated in it, sorting out the data will be placed in it.

If you think it’s written well, click a “like” and add a follow! Point attention, do not get lost, continue to update!!