A self-balancing binary search capable distributed database (DB) includes a number of computing devices associated with a communication system and/or network. Each of the respective computing devices forming the distributed DB stores a subset of the overall information included within the distributed DB. Based on keys of key-value pairs (KVPs) stored in the computing devices, the computing devices are arranged logically to form a sorted key-ordered ring such that each computing device includes KVPs with keys higher than a predecessor computing device and lower than a successor computing device. A requested KVP query is made to any computing device in the distributed DB, which may include generating and transmitting another query to one or more other computing devices until the requested KVP is found. The distributed DB performs balancing operations moving the KVPs from computing devices with higher storage usage to computing devices with lower storage usage.