NoSQL or RDBMS for a Giant Lookup Table? What is the best way store leaked website credentials? I've come up with two that would get the job done for the most part, but I am trying to find the fastest and most efficient solution.

Take for example this site, which has a pretty basic search from the look of it, a more basic example would be the site haveibeenpwned. Doing a small scale test, so really I have two questions, first, would this be a good fit for a NoSQL style database? Or should I stick with a RDBMS? The second question is which structure would be able to return the results the fastest (and most completely)? 

I could do it with something like this, but it would have lots of redundant information: 

{   "uiid": "18c13cb5-bb91-41c6-8267-fd35e868d4c0",
    "username": "foouser",
    "email": "foo@bar.tld",
    "ip": "127.0.0.1",
    "fullname": "Koolaid Man",
    "phonenumber": "+1800123456",
        "creds":    [{
        "hash": "1ed6c8f1465d39e64055e18762fca52850244c9aed2158d6e63406693e775b4a",
        "algo": "sha256",
        "salt": "andpepper",
        "plaintext": "iesh0oow3ieg4thoweonga5aengeaGee3xahbohCuu6oog7oorei2jooPi1hooR6Shi9aoji7wu8ahreeG4see7Thothoo2ev7ch",
        "dateadded": "2012-04-23T18:25:43.511Z"
        },
        {
        "hash": "1ed6c8f1465d39e64055e18762fca52850244c9aed2158d6e63406693e775b4a",
        "algo": "sha256",
        "dateadded": "2012-04-23T18:25:43.511Z"
        }
        ]
}


Using a RDMS, I could so something like this: 

CREATE TABLE `identities` (
    `uiid`  UUID NOT NULL UNIQUE,
    `email` INTEGER,
    `username`  INTEGER,
    `fullname`  INTEGER,
    `ip`    INTEGER,
    -- ...
);
CREATE TABLE `hashed_plain` (
    `uhid`  UUID NOT NULL UNIQUE,
    `type`  INTEGER,
    `hash`  TEXT NOT NULL UNIQUE,
    `salt`  INTEGER,
    `plain_text`    INTEGER NOT NULL,
    -- ...
);
CREATE TABLE `hash_instance` (
    `id`    UUID NOT NULL PRIMARY KEY UNIQUE,
    `uhid`  TEXT,
    `uiid`  TEXT,
    -- ...
);
-- ...


I know that both of these are not very good implementations, hopefully someone more knowledgeable than myself can point me in the right direction. 


There Are Many "People" (by this I mean the information that identifies the user : username, email, ip ,name, etc.)
There are many "Keys" (by this I mean the information that validates the person: password, hash, salt, etc.)
Each Person can have many keys
Each Key can have many People


I want to be able to search by any field (with the exception of the UUID's) and return everything else associated with that piece of information.  What's the best way to do that?
As for NoSQL vs Relational, Postgres gives you the best of both but with the benefit of ACID. Along with its robust reliable relational engine, the JSONB data type allows you to save JSON data, internally stored in an optimized binary format that provides for indexing individual attributes. So you get the flexibility of less-structured data (JSON) with the very fast performance of Postgres indexed queries.

Also, Postgres supports UUID as a data type, storing the native 128-bit values. Support includes indexing and use as primary key. 

As for your database structure, while I am do not know your data well, it appears from your example data that have a simple parent-child relationship between an "identity" or "login" or whatever you want to call it, and a "cred". On the cred table, for rows without a salt, just leave the extra fields null or with empty text ('').

Your description suggests you have a many-to-many between Person and Key entities. If so, in a relational database a many-to-many is always represented with a third table containing at lead two fields, the key of each table, so a pair of foreign keys. Classic example: Book table and Author table are connected by an Authorship table contains an Author ID and a Book ID for each author contributing to each book. 

Tip: devise another name for your Key entity as the word key is, well, key to deigning and using a database. So, "key" is a confusing entity name.

Seems like you should be able to store all this data relationally rather than as JSON. But Postgres gives you both options.