About indexing

simo idra at samba.org
Thu Dec 27 17:48:03 MST 2012

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.


Simo Sorce
Samba Team GPL Compliance Officer <simo at samba.org>
Principal Software Engineer at Red Hat, Inc. <simo at redhat.com>

More information about the samba-technical mailing list