A storage structure for B-trees is presented which is robust, in that many errors and combinations of errors in its structural data can be detected and corrected. The structure presented here is superior to a previous robust B-tree in a number of ways: insertion and deletion are simpler, the classes of errors which can be detected and corrected are larger, and it is simpler to implement a correction routine. These advantages are achieved without any significant increase in cost; storage space requirements and update time are almost unchanged. This paper describes briefly both the old and new B-tree implementations, and makes comparisons between them.