The LZ-based compression schemes are based on finding and eliminating repeated strings of characters. As they compress a stream, they build up a dictionary of strings that have been encountered, so when the same string is encountered again, they transmit the location of that string in the dictionary instead of re-transmitting the entire string.
In a typical case, the first few kilobytes of data actually expand a little, because the dictionary starts out (essentially1) empty. Only after a few kilobytes have been scanned and strings added to the dictionary do you start to get much compression.
To get such an algorithm to work decently on record-oriented data, you probably want to group your records into blocks of, say, something like 64K apiece. Reading a record will be a two-step process. First you'll find the block that contains the record, read it into memory, and de-compress the whole block. Then you'll find the record you care about in that decompressed data.
The block size you select is a compromise between compression efficiency and random access efficiency. A larger block generally improves compression, but (obviously enough) requires you to read more data to get to the records in a block. A smaller block size reduces the extra data you need to read to get to a particular record, but also reduces compression.
If you're willing to hand-roll your compression, you can do things rather differently. The general idea would be to scan through a large quantity of data to build a (roughly LZ-like) dictionary of repeated strings, but not do on-the-fly compression like LZ does. Instead, store the dictionary (separately from the data). After you've scanned through all the data, use the full dictionary to compress the data. This requires you to store the dictionary (which uses some space) but allows you to have it pre-built when you decompress the data. This reduces the penalty for compressing each record separately, so when you read data you'll only need to read one record (plus associated parts of the dictionary -- but when it's in use, you'll probably have most of the dictionary in RAM most of the time).
1 In quite a few implementations, the dictionary starts out initialized with entries for the 256 possible byte values, but this still results in expansion -- each of those one-character strings is represented in the bit-stream with a (minimum of a) 9-bit code. In other cases, those dictionary entries are "virtual" -- each is treated as being present at the proper position in the dictionary, but never actually stored.