As relational DBMSs become more and more popular and as organizations grow. the sizes of individual tables are increasing dramatically. unfortunately, current DBMSs do not allow updates to be performed on a table while an index (e.g.,a B+ -tree) is being built for that table,thereby decreasing the systems' availability. this paper describes two algorithms in order to relax this restriction. our emphasis has been to maximize concurrency, minimize overheads and cover all aspects of the problem. builds of both unique and nonunique indexes are handled correctly. we also describe techniques for making the index-building operation restartable, without loss of all work, in case a system failurewere to interrupt the completion of the creation of the index. in this connection, we also present algorithms for making a long a sort operation restartable. these include algorithms for the sort and marge phases of sorting.