I read an article some time ago in the german C64 Magazine. The bullets are characters that act as sprites as someone already pointed out. Ship and enemies are sprites.
Levels are made of characters also but with a twist. Since the levels are so huge, and memory is precious, Trenz wrote his own set of tools to group characters into modules.
So he can use bigger modules and compose those. Also he would use certain patch-modules to get the intersection of modules nice and clean.
All in all its a kind of compression, where levels are described building blocks instead of char by char.
Also you might noticed that in Katakis some levels have parallax backgrounds.
That is made by having a pattern to fill the background, mostly made of 2x2 or 3x3 characters, and animating it (bit-shifting) against the direction of scrolling. E.g. the level scrolls 2 pixels to the left, the background-pattern is scrolled 1 pixel to the right, hence it appears to be scrolled at a slower pace.
Hope that helps
One more thing you can actually see the single modules and such here https://archive.org/details/64er_1989_10/page/n27 scroll to page 24