Provided are a method, system, and program for managing a database. A request is processed to create an index on at least one key column of a table in a computer readable medium. A determination is made of table partitions in which rows of the table are stored. One index partition is generated for each determined table partition, wherein each index partition includes nodes, wherein each node in each index partition includes a key value from at least one column in a corresponding table row in the table partition associated with the index partition and a location identifier identifying the corresponding table row in the corresponding table partition. In certain embodiments, a technique is implemented during queries to limit the search to a subset of the multiple index partitions when possible and return rows in the order of the key columns of the index while the same range of key values can exist across multiple index partitions.