Methods, apparatus, and computer-readable media for providing a device handle database in an EFI environment are disclosed. According to one method, a device handle database is created for storing data identifying the protocols that have been installed on one or more device handles. The database includes a sorted array of elements utilized to store protocol data for a family of protocols having the same GUID. Each element in the array comprises a family data structure including a field for storing the GUID for the family along with a field for storing a pointer to a linked list that stores the protocol instance data for each of the protocols in the family. Each node in the linked list is also a member of a linked list for storing protocol data for all of the protocols installed on a given device handle.