Non-volatile memory devices logically organized to have erase blocks of at least two different sizes provide for concurrent erasure of multiple physical blocks of memory cells, while providing for individual selection of those physical blocks for read and program operations. In this manner, data expected to require frequent updating can be stored in locations corresponding to first erase blocks having a first size while data expected to require relatively infrequent updating can be stored in locations corresponding to second erase blocks larger than the first erase blocks. Storing data expected to require relatively more frequent updating in smaller logical memory blocks facilitates a reduction in unnecessary erasing of memory cells. In addition, by providing for larger logical memory blocks for storing data expected to require relatively less frequent updating, efficiencies can be obtained in erasing larger quantities of memory cells concurrently.