Avoid decrypting every password in a password manager The Setup

I'm making a password manager for fun. It stores a random encryption key, encrypted with a key derived from the master password, and then it stores the data, which is a list of (site, username, password) triples, encrypted with the encryption key. Here, encryption means calling libsodium's secretbox, which is authenticated encryption.

The Problem

I wanted to avoid decrypting every single password just to get a single one. Since the database still needs to be searchable, all the metadata still needs to be unencrypted in one go. So I came up with two different strategies:


Keep the passwords in a separate dictionary, indexed by hash(encryption_key ++ data).
Encrypt the password before storing it in the triple, which is then encrypted again. This idea sounds terrible, because double encryption scares me.


My questions are:


Is my setup secure?
Is it reasonable to avoid decrypting every password?
Which of the two aforementioned strategies are secure, and is there a simpler way to encrypt passwords only as necessary?


Sorry if this question is too specific, I'd be happy to try to make it more general.
I understand your design goal, but I see an issue in that you propose to encrypt the metadata alongside the passwords.  Searching is made more complicated because you have to decrypt the database to expose the metadata to search for the associated password.

Instead, consider storing only encrypted, unique passwords in your database, indexed by a secure hash of the site/username metadata.  For any new site that requires a password, locate a slot indexed by $H(meta)$. Generate a unique password for that site, encrypt it with the master, and store it at the hash slot. Give the plaintext to the website.  

To access the password later, reverse the steps.  This lets you encrypt only the passwords, and uses a strong hash function to protect the mapping between the site and the password even in the event of a disclosure of the master password.

[A few edits later,] Here is a protocol that might work.  It assumes you have a secure hash function $H$, a wallet $W$ indexable as a dictionary with no entries to start, and a secure master password $m$.  Assume $E_p(data)$ means to encrypt data with key $p$, and $D_p(data)$ means to decrypt.  Let $meta$ be a tuple representing the site name, user name, cookie, or anything else that makes sense to include for retrieving a password.

When visiting a site $s$:


Let $i \leftarrow H(meta)$.
If $i \not \in W$, then this is the first visit to the site (with this meta tuple); generate unique password $p_s$ (conforming to the policy at $s$) and encrypt with $E_m(p_s)$ and store at $W[i]$.
If $i \in W$, then site has been visited before, therefore retrieve site password $p_s \leftarrow D_m(W[i])$.


The benefits are that you decrypt only a single password for each site $s$.  The master password $m$ is used only for site password protection, not for the metadata.  The identity of the sites and meta information are protected with a hash function.  With a fast implementation of $W$, lookup can be as fast as $O(1)$.  A dictionary indexed by a hash can grow dynamically, better than my previous edit.  

On the downside, if the adversary has access to $W$ and meta information on $s$, he can tell that you have an account on that site.  By encrypting the entire database including metadata, your original design is secure against this threat.

I haven't thought more than a day on this, so there may be a weakness - hopefully someone will comment and I'll continue to revise it.