Die Meldung "Nicht genügend Speicher" bei der Installation von Apps und freier Speicher beim Blick in den Dateimanager (bzw. im Einstellungsmenü) beziehen sich auf unterschiedlichen physischen Speicher.
Der App-Speicher sollte in frühen Androidversionen mit einem schnellen Speicherbus an die CPU gebunden werden, und der Benutzerspeicher über eine emulierte USB-Verbindung. Deshalb heisst auch heute noch der interne Benutzerspeicher "sdcard" obwohl er keine SD-Karte ist.
Physisch wird der Benutzerspeicher auf /data/media eingebunden und /sdcard ist ein Symlink dorthin.
Deshalb kann auch (meistens) /data formatiert werden ohne die Bilder etc. unterhalb /data/media zu verlieren (in Standardeinstellung wird nur innerhalb eines Devices formatiert und nicht innerhalb eines Dateisystems).
Wenn Du also AppSpeicher aufräumen willst, musst Du das Handy rooten und dann mit Kommandozeilentools diesen AppSpeicher angucken (alles innerhalb /data UND ausserhalb /data/media). Oftmals sind dort Dateien übriggeblieben die einerseits keinem gehören und andererseits sich keine App traut die zu löschen (weil die App nicht wissen kann OB die jemandem gehören). Kandidaten sind z.B. Thumbnail-Datenbanken und Vorschaubilder etc.
Genau das ist einer der Gründe warum bei einem Wechsel des OS die Partition /data IMMER formatiert und nicht nur gelöscht werden sollte.
Wer allerdings LOS und den LOS-Updater nutzt sollte als Erstes gucken, daß die ROMs nach der Installation gelöscht werden. Die machen nämlich genau diesen AppSpeicher voll (/data/lineageos_updates).
VG
Google Pixel 3 mit LOS17.1