How to optimize mySQL query with indexes when column contains duplicate values

I am trying to retrieve all messages from a table whose latitude and longitude values fall within a certain n meter radius. $messages = DB::table('messages')->select('*') ->whereBetween( 'latitude', array($userLatitudeFloor, $userLatitudeCeil) ) ->whereBetween( 'longitude', array($userLongitudeCeil, $userLongitudeFloor) ) ->where('message_permission', 'public') ->orderBy('timestamp', 'DESC') ->take(100) ->get(); In attempting to optimize the query time, I tried to utilize a Primary Key index on the on the latitude column. However it appears that mySQL does not allow indexes to be created when the column contains duplicate values e.g. My question is there a way to use indexes when the column contains duplicate values or does mySQL offer an alternative method. Indexing might be the wrong route to take here in order to mitigate the search query time. If so, any suggestions for alternative methods are more than welcome. Thanks in advance