About indexing

[Matthieu Patou]

On 12/27/2012 04:48 PM, simo wrote:
> On Thu, 2012-12-27 at 15:36 -0800, Matthieu Patou wrote:
>> Hi Tridge,
>>
>> 2 years ago at SDC I remember that you made an explanation on indexing
>> and how to improve things.
>> As I'm working on indexing stuff in TDB/LDB I'm trying to recall the
>> details of this discussion as I kind of remember that you said that it
>> could bring good improvements.
>> The fact is that I don't remember all of it, maybe you do ?
>>
>> In order to help you to recover your memory I know for sure that at some
>> point you talked about having 1 index sorted and because maintaining a
>> sorted index can be expansive there was a potential second index (or
>> overflow index) that was not sorted and that was at most
>> sqrt(len(index1)) long in order to keep the search O(sqrt(n)/2).
>>
>> I put Nadya in copy as she was also present during the explanation.
> Hey Matthieu, have you looked into how OpenLDAP or 389ds organized
> indexes ? I guess you might find good inspiration there.
Not yet but I would rather first to manage to remember what I was told 
as it seems reasonable at that time.
But still I have plans to see the code of openldap to see how certains 
indexes are done.

-- 
Matthieu Patou
Samba Team
http://samba.org