When the file is large, and in direct access devices such as disk or the like, in order to reduce the number of read-write times of the disk during the lookup process, improve the search efficiency, the read and write operation based on direct access device is "page" unit Characteristics.
In 1972 R. Bayer and E.MCCREight proposed a multi-way balanced tree called B-tree. It is suitable for direct access to dynamic lookup tables on the device or the like.
Definition of B- Tree 1, definition of B-tree
A M (M ≥ 3) order B-tree is a M fork tree that meets the following nature:
(1) Each node contains at least the following data domain:
(j, p
0, K
L, P
1, K
2, ..., k
I, P
i)
among them:
J is the total number of keywords
K
I (1 ≤ i ≤ j) is a keyword, keyword sequence is incremented Order: K
1 2 <... i. P i (0≤i≤j) is a child pointer. For leaf junctions, each P i is an empty pointer. note: 1 Practical in saving space, can save the needle domain in the leaf junction point i, but must add a logo field LEAF in each node, which is true to indicate the leaf node, otherwise it is an internal node. 2 In each internal node, it is assumed that all keywords in the subtree Pi are used to use Keys (PI). Keys (p) 0) 1 1) 2 <... i i) That is, the keyword is the split point, all keywords in the left son tree are less than K I, all keywords in the right sub-tree are greater than k i. (2) All leaves are on the same layer, the number of leaves is the height H of the tree. (3) The number of keywords included in each non-root point is satisfied: . That is, each non-root point should be at least Keywords, at most M-1 keywords. Because the degree of each internal node is exactly the total number of keywords plus 1, there is at least the internal node of each non-root. Sub trees, at most M pieces. (4) If the tree is non-empty, then there is at least one keyword, so that the root is not a leaf, it has at least 2 sub-trees. There are many M-1 keywords, so there are M pieces.
