Note that I am not a crypto systems or security expert. This is what I've seen done and it makes sense, but I cannot claim it doesn't have security issues beyond what I outline below. As always, get a proper security audit if it's important.
In the following, "credential" can refer to ssh keys, passwords, or whatever needs storing.
The typical model is to use a couple of levels of crypto.
For each user, generate and store a public/private keypair
Store the public part of the user's key in the clear in the user's record
Store the private part of the user's key encrypted to the user's passphrase in the user's record.
Encrypt each credential to a symmetric key that's unique to that credential
Encrypt each credential's symmetric key to the public key of every user who should have access to that key, and store the resulting encrypted material in a user_credentials
mapping table.
Essentially, you maintain a keyring, much like the gpg keyring where the public part is in cleartext and the private part is encrypted to a passphrase. You should make sure the passphrase selected by each user is strong.
Now you can generate a symmetric key for each encrypted credential. Encrypt this key to every user's public key and store it in a user-credentials join table. Never store this symmetric key unencrypted, and use a different symmetric key for each credential.
You land up with something like this
[user]
user_id
username
login_password_salt
login_password_hash
public_key_text
private_key_sym_encrypted_to_passphrase
[user_credential]
user_id
credential_id
credential_key_encrypted_to_user_public_key
[credential]
credential_id
credential_data_encrypted_to_credential_key
There are quite a few advantages to doing things this way:
If a dump of your database is leaked your credentials are still safe, or as safe as your passphrases and key strengths.
Since you have a different symmetric key for each credential you can control which users have access to which credentials
Any user with access to a given credential can give another user access to it; they just decrypt it using their key and encrypt it to the other user's public key. You don't need to get everybody together to add credentials or add new users.
Because you're encrypting each credential to a symmetric key, and then encrypting that key to the user's key, you can change the stored credential without having to re-encrypt it to each user's key. It just makes updating stored credentials more convenient.
However, if the database host is compromised, an attacker can easily extract the passwords any given user has access to as soon as that user logs in. They capture the user's passphrase by wrapping functions or by enabled detailed logging and searching the logs. Then they can decrypt passwords in a stolen dump or from the live DB. A compromised database host is no danger until a user logs in to use it but then all is lost.
This means that the host of the database is security critical. Leaking the dump isn't fatal to security, but someone being able to modify the code running on the DB is a fatal security breach.
In addition to using your credentials management DB to extract ssh key material, passwords, etc when you need it, you can also use it as an authentication proxy where it can auth against a service without your user having to ever be able to learn the credential used. For example, your app might decrypt an ssh key, add it to an ssh agent, and use the decypted key to log in to a server via the agent without the user ever being able to see and access the key directly.
Masi,
The PostgreSQL B-Tree index is very strongly based on the implementation by Lehman and Yao, which includes a lot of work oriented around multi-version concurrency control, but there's still great info in this paper.
Of course, PostgreSQL doesn't make a 100% accurate replica of the method in the paper, and to find the differences, there will be almost no way to do it other than to (1) find someone who understands the PostgreSQL B-Tree, and has the time to go through the intricate explanation, or (2) dig through the source code yourself.
Another possibility is for you to visit Bruce Momjian's excellent reference website, where he discusses PostgreSQL internals in more detail.
In this case, however, based on the nature of your questions, I feel like you may have a fundamental misunderstanding about how B-Tree indexes work. In this case, I think a little Google searching, or maybe reading through a portion of a textbook like Fundamentals of Database Systems by Elmasri & Navathe would do you some good.
Best Answer
I think it is opportune to start pointing out that, in a relational database —as per Dr. E.F. Codd— information is represented by means of one and only one structure, the relation, which is usually portrayed as a table.
The relational model deals exclusively with aspects of the logical level of abstraction, so a table (an abstraction) is part of the logical level of a database (it is susceptible of undergoing logical operations, e.g., projections, joins, restrictions, etc.), so it is completely independent from the physical storage utlized by the database management system (DBMS for brevity) of use.
That being so, since the relational model has to do solely with logical-level aspects, it offers physical data independence, which sets DBMS (e.g., SQL platforms like IBM DB2, Microsoft SQL Server, PostgreSQL, etc. —that although quite powerful, strictly speaking, are semi-relational, i.e., they do not comply fully with the stipulations of the relational framework—) free to (a) store at the physical level of abstraction in any way their developers/vendors deem convenient (b) the data represented via logical-level tables.
It is important to note that the physical-level storage can in turn be divided in distinct sub-levels of abstraction.
Therefore, the physical arrangements depend on the particular DBMS under consideration, hence they can vary from platform to platform.
Examples of physical structures utilized by different SQL platforms are detailed
In case you are interested, you may find of help this answer to a question about some of the different levels of abstraction of a computerized information system.