@aditya: hashing is not good because of space wastage. For indexing B+ trees are used almost everywhere.. like ur NTFS file system and MySQL database.
However, hashed B tree is a real nice idea.. used in ext4 filesystems for metadata indexing, Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay On Wed, Dec 9, 2009 at 8:13 PM, Aditya Shankar <iitm.adityashan...@gmail.com > wrote: > > > On Wed, Dec 9, 2009 at 7:48 PM, Aditya Shankar < > iitm.adityashan...@gmail.com> wrote: > >> Hi, >> >> On Wed, Dec 9, 2009 at 2:53 PM, Manisha <pgo...@gmail.com> wrote: >> >>> We have a server hit by millions of users. Sever log files contains >>> the user ids of all of them. How do we find the frequency of login of >>> each user. What will the most efficient way to store the users, and >>> access them to find their frequency(The log files are very huge!!) >>> >> oops... > >> Can't we just use a hash table? It's O(1) access, addition and updation >> (and removal for that matter). >> > There will not be conflicts because the user IDs are presumably unique. >> >>> >>> I thought of using B+ tree indexing with user ids as the key. Leaf >>> nodes will have the pointers to bucket of user ids. One item of bucket >>> will contain user id and frequency of this user. >>> For insertion, search complexity will be ~O(logn) >>> >>> Any potential problem with approach? Are there any better approach to >>> tackle this problem? >>> >>> -- >>> >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >>> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
