, , . AVL-, , .. . . , .
, , . , - 2 . , -1 . , , . . 22 , . , , . , J .
. 22.
, , . , .
. . 23 .
. 23.
, -1 . . -1 , . .
-
- . , , . , .
, , . , . , - - (top-down B-trees).
, . - , . , -, .
|
|
, . , , . , , , , .
+
- . - , . , . . , , . , , .
, - . , . , , , . - + (B+tree).
+ , . .
.
2.1 [16]
, , , , , .
, Rj R1,...,Rj-1 . , .
. 1 < j < N R1,...,Rj-1 , K1<=K2<=<=Kj-1. Kj Kj-1, Kj-2... , , Rj Ri Ri+1. Ri+1,..., Rj-1 i + 1. , . Rj "" , .