Provided are a computer program product, system, and method for generating sub-indexes from an index to compress the index. An index has levels of nodes for a composite key comprised of component keys. Each node includes at least one composite key value comprised of component key values. A plurality of sub-indexes is generated including one sub-index for each component key of the composite key. Nodes are generated in each sub-index corresponding to nodes in the index. In each node of the nodes of the sub-index, a component key value is generated, for the component key for which the sub-index was generated, from at least one composite key value in the corresponding node of the index. The sub-indexes are used to search for a record matching a search composite key value in the database using component key values of the search composite key value.