Maybe you search VIM instead of VI-tiny ... by default it's a slim version of VIM in Debian
edit :
The full version of VIM is around 25Mo

(VIM + VIM-common + VIM-runtime)
VIM-tiny is around 2Mo (VIM-tiny + VIM-common)
Personally, I can't tolerate vim-tiny as it behaves quite differently than vim (full), so I purge tiny and install the full one. My install is on an SD card, so room is not a problem. I'm just more use to vim than nano, so that's my preference.
feffer