Jag tror att frågan du har förmodligen matchar en stor andel av data i tabellen. I sådana här situationer väljer MySQL-optimeraren ofta att göra en tabellskanning och ignorera index helt, eftersom det faktiskt är snabbare än att gå igenom besväret med ytterligare läsning av hela indexet och använda det för att plocka ut data. Så i det här fallet gissar jag att public_private='yes' and approved='yes' matchar en bra del av ditt bord. Därför, om MySQL hoppar över att använda indexet på grund av detta, är det inte heller tillgängligt för sortering.
Om du verkligen vill att den ska använda ett index, då skulle lösningen vara att använda FORCE INDEX :
select * from videos FORCE INDEX (approved_2) where public_private='public' and approved='yes' order by number_of_views desc;
Jag skulle dock köra några tester för att se till att det du får faktiskt är snabbare än vad MySQL-optimeraren har valt att göra. Tydligen optimeraren har vissa problem med att göra val för beställning, så du kan definitivt prova detta och se om du får förbättrad prestanda.