A computer storage device having a host interface, a controller, non-volatile storage media, and firmware. The firmware instructs the controller to: receive, via the host interface, a request from a host to allocate a namespace of a quantity of non-volatile memory; generate, in response to the request, a namespace map identifying a plurality of blocks of addresses having a same predetermined block size, and a partial block of addresses having a size smaller than the predetermined block size; and convert, using the namespace map, logical addresses in the namespace communicated from the host to physical addresses for the quantity of the non-volatile memory. For example, the request for allocating the namespace can be in accordance with an NVMe protocol.