+-tree in +-treeeach node stores up to references to children and up to keys each reference is considered "betweentwo of the node' keysit references the root of subtree for which all values are between these two keys here is fairly small tree using as our value for +-tree requires that each leaf be the same distance from the rootas in this picturewhere searching for any of the values (all listed on the bottom levelwill involve loading three nodes from the disk (the root blocka second-level blockand leafin practiced will be larger -as largein factas it takes to fill disk block suppose block is kbour keys are -byte integersand each reference is -byte file offset then we' choose to be the largest value so that ( < solving this inequality for dwe end up with < so we' use for as you can seed can be large +-tree maintains the following invariantsevery node has one more references than it has keys all leaves are at the same distance from the root for every non-leaf node with being the number of keys in nall keys in the first child' subtree are less than ' first keyand all keys in the ith child' subtree ( < <kare between the ( )th key of and the ith key of the root has at least two children every non-leafnon-root node has at least floor( children