This paper considers the construction of optimal search trees for a sequence of n keys of varying sizes, under various cost measures. Constructing optimal search cost multiway trees is NP-hard, although it can be done in pseudo-polynomial time O3 and space O2, where L is the page size limit. An optimal space multiway search tree is obtained in O3 time and O2 space, while an optimal height tree in O(n2 log2n) time and O(n) space both having additionally minimal root sizes. The monotonicity principle does not hold for the above cases. Finding optimal search cost weak B-trees is NP-hard, but a weak B-tree of height 2 and minimal root size can be constructed in O(n log n) time. In addition, if its root is restricted to contain M keys then a different algorithm is applied, having time complexity O(nM log n). The latter solves a problem posed by McCreight.