Address Book Search - Which Data structure i should use when large data

Question

I want to design Address book with following fields

UID Name PhoneNumber1 PhoneNumber2

UID is to identify the name uniquely. Lets say i want to save 2 million records. Now i want to structure how to save this records, so that it can be searchable by both Name and phoneNumber.

Which data structure and search technique i should go with.

Thanks in advance

score 1 · Answer 1 · answered Dec 08 '15 at 04:31

What if you have conflicting names? John Smith could return multiple times. It appears that you are better off just using PhoneNumber1/PhoneNumber2 as your search variables.

I'd recommend a HashTable to do this, as it allows O(1) for searching, and with 2 million records, you don't want it to take forever to find someone.

score 1 · Answer 2 · answered Dec 08 '15 at 05:01

Normalise that to the following tables and columns:

Names: UID, Name
PhoneNumbers: UID, SN, PhoneNumber
- SN serial number, so 1 or 2 (and in the future, 3 to 1000 as well)

Each search you do should run two queries, one for each table (or one UNION query on both tables)

SELECT   UID, Name
FROM     Names
WHERE    Name = '%<search string>%'

SELECT   UID, PhoneNumber
FROM     PhoneNumbers
WHERE    PhoneNumber = '%<search string>%'
ORDER BY UID  # so that multiple matches with same user appear together

Combining the results of both queries can be done in Java.

score 1 · Answer 3 · answered Dec 08 '15 at 05:28

Why don't you design a class AddressBook

class AddressBook{
private Integer uuid;
private String name;
private Integer phoneNumber1;
private Integer phoneNumber2;

//getters & setters 

}

Create a AddressBook Table in your database with the corresponding fields. uuid will be the primary key. Persist the AddressBook object.

To search by name

select * from AddressBook where name ="something";

To search by phone number

select * from AddressBook where phoneNumber1="something";

score 0 · Answer 4 · edited May 23 '17 at 12:23

That depends on what are your main targets :

If requirement dvelopment is done and you have decided to use a relational data model for data storage and retrieval then @aneroid answer is an option.
Have in mind that:

Using WHERE Name = '%<search string>%' will force a considerable cost on RDMS engine. You may seek advanced full text search techniques in large scale data, based on your RDBMS.
If performance is the main target, using relational in memory databases will be an option.

In case RDBMS can be skipped, then java lang data structures will come in handy, see here they are forged in terms of time complexity.

Address Book Search - Which Data structure i should use when large data

4 Answers4