Historically, I don't think there was much concern in the US over library records. Before library records were computerized it was often easy for anyone to find out who had checked out a given book and when.
A typical system might work like this. Inside each book there was a pocket attached to the back of the front cover, and in that pocket was a card.
When you checked out the book, your name and library card number and when the book was due were added to the card, below the entries for previous checkouts, and the card was filed somewhere. A card showing the due date was placed in the pocket and you could then leave with the book.
When you returned the book the checkout record card was put back in and the book re-shelved.
Want to know who has checked out a book before? Just walk into the library and look at the checkout card. No need for a warrant, and no need to even ask a librarian for the records.
Eventually the card would fill up and they'd have to start a new one. I don't know if they kept the old ones or not. Since storing them would take space, I'd guess they were probably thrown away (perhaps after recording some stats on how frequently the book was checked out, because those might be useful in the future when deciding on changes to their collection). If they were thrown away, I don't know if they would have taken care to destroy them or just toss them in the garbage.