آبشاره‌سازی جزءبه‌جزء
آبشاره‌سازی جزءبه‌جزء پویا

در آبشاره‌سازی جزءبه‌جزء به صورت پویا، لیستی که در هر گره از گراف کاتالوگ ذخیره شده‌است، می‌تواند به صورت پویا تغییر کند. به عبارتی اجزای این لیست می‌توانند به روز شوند و یک عضو در آن درج شود یا از آن حذف گردد. ایجاد این تغییرات باعث به وجود آمدن مشکلاتی در ساختاربندی داده‌ها می‌شود.
یکی از مشکلاتی که در این زمینه وجود دارد این است که هنگام اضافه شدن یک عضو به یک گره یا حذف شدن عضوی از آن، تغییراتی در لیست مربوط به آن گره ایجاد می‌شود. از طرفی تغییر در یک لیست منجر به وجود آمدن تغییرات در سایر لیست‌ها در سایر گره‌ها نیز می‌گردد. برای حل این مشکل، به جای استفاده از یک آرایهٔ مرتب شده برای هر گره، از یک درخت دودویی جستجو استفاده می‌شود. با این کار دو هدف برآورده خواهد شد. با استفاده از درخت دودویی جستجو، امکان به روز رسانی سایر گره‌ها هنگام تغییر یک گره، با تعداد عملیاتی محدود فراهم می‌شود و همچنین توانایی جستجوی دودویی پابرجا باقی خواهد ماند.
همان‌طور که پیش‌تر گفته شد، هر گره از گراف کاتالوگ، تعدادی از اعضای لیست همسایهٔ خود را نیز نگه‌داری می‌کند. به عبارتی در لیست یک گره، اعضایی که در مکان d از لیست همسایه قرار دارند نیز وجود دارد. در برخی شرایط با توجه به مقدار d و همچنین اعضای یک لیست، این امکان وجود دارد که با هر به روز رسانی و تغییر در یک لیست، لیست‌های همسایه نیز تغییر کنند. برای حل این مشکل از روشی شبیه به روش ساخت داده ساختار B tree استفاده می‌شود. با استفاده از این روش، می‌توان اطمینان حاصل کرد که تعداد داده‌هایی که انتخاب می‌شوند، کمتر از کل داده‌های لیست تقسیم بر d است و همچنین این اعداد در مکان‌های ثابتی از لیست قرار دارند. این موضوع باعث می‌شود که انتقال تغییرات هنگام درج یا حذف برای یک لیست از یک گره، تعداد عملیاتی کمتر از یک تقسیم بر d نیاز داشته باشد. یعنی یک تغییر در یک گره، به طور میانگین حداکثر یک تقسیم بر d تغییر برای به روز رسانی سایر گره‌ها نیاز دارد. با این روش، توزیع داده‌ها در میان گره‌ها به گونه‌ای خواهد بود که میانگین تعداد عملیاتی که برای به روز رسانی درخت‌های جستجوی دودویی صورت می‌گیرد، عددی ثابت است.
مسئلهٔ اصلی در مبحث پویا کردن آبشاره‌سازی جزءبه‌جزء، نگه‌داری اندیس‌ها می‌باشد. همان‌طور که پیش‌تر گفته شد، هر عضو از لیست موجود در یک گره، دو اندیس را نگه می‌دارد. یکی اندیس مربوط به جستجوی خودش در همان لیست و یکی اندیس مربوط به جستجوی آن عضو در لیست همسایه. نگه‌داری این اندیس‌ها به صورت پویا هزینه‌بر است، چراکه با تغییر یک عضو، تعداد اندیس‌هایی که در تمام لیست‌ها باید تغییر کند، عدد بسیار بزرگی خواهد بود. برای همین، در این مدل، داده ساختارهای دیگری برای ذخیره شدن در هر گره، در نظر گرفته می‌شود که به شرح زیر می‌باشند:
یک نگاشت از اجزای لیست مربوط به یک گره، به اعداد صحیح کوچک؛ بنابراین برای بررسی ترتیب قرار گیری عناصر یک لیست، کافیست این اعداد صحیح نسبت داده شده به آن‌ها را با هم مقایسه کرد و با انجام عملیات بر عکس این نگاشت می‌توان از اعداد صحیح به اجزای اصلی لیست، دست یافت. روشی که Dietz در سال ۱۹۸۲ به آن دست یافت، راهکاری می‌دهد تا این نگاشت به صورت کارایی ذخیره شود؛ بنابراین هر گره، این نگاشت را ذخیره می‌کند و تنها با داشتن همین نگاشت می‌توان از اعضای لیست به لیستی از اعداد صحیح کوچک‌تر و برعکس دست یافت.
داده ساختاری برای جستجوی اعداد صحیح (داده ساختاری مانند van Emde Boas tree). با استفاده از این داده ساختار، می‌توان در میان اعداد صحیح نسبت داده شده به اعضای لیست، که طبق نگاشت گفته شده حاصل می‌شوند، به جستجوی عدد مورد نظر پرداخت.
برای هر گره همسایه در گراف کاتالوگ، یک داده ساختار جستجوگر اعداد صحیح مشابه برای زیر مجموعه‌ای از اعداد به دست آمده از آن گره در نظر گرفته می‌شود. به وسیلهٔ این داده ساختار و نگاشت اعضای لیست به اعداد صحیح، به صورت مؤثر می‌توان هر عضو x لیست آن گره را در تعداد مراحل ثابت پیدا کرد.
این داده ساختارها باعث می‌شوند که آبشاره‌سازی پویا در مرتبهٔ زمانی (O(log n برای هر درج و حذف عمل کند. همچنین یک زنجیره از k عمل جستجوی دودویی که در یک مسیر به طول k در گراف کاتالوگ صورت می‌گیرد، در مرتبهٔ زمانی (O(log n + k log log n انجام پذیرد.