Provided are a computer program product, system, and method for selecting pages implementing leaf nodes and internal nodes of a data set index for reuse in memory. Pages in the memory are allocated to internal nodes and leaf nodes of a tree data structure representing all or a portion of a data set index for the data set, wherein the leaf nodes include information on members of the data set. The internal nodes include one or more keys used to traverse the tree data structure to reach the leaf nodes to access the members of the data set. At least one page allocated to the leaf nodes and the internal nodes is selected based on durations during which the allocated pages have not been used. Pages allocated to the leaf nodes are selected for reuse at a higher rate than the pages allocated to the internal nodes.