A search optimized for new heavy particles decaying to two $b$-quarks and produced in association with additional $b$-quarks is reported. The sensitivity is improved by $b$-tagging at least one lower-$pT$ jet in addition to the two highest-$pT$ jets. The data used in this search correspond to an integrated luminosity of 103 $fb-1$ collected with a dedicated trijet trigger during the 2017 and 2018 $s=13$ TeV proton-proton collision runs with the ATLAS detector at the LHC. The search looks for resonant peaks in the $b$-tagged dijet invariant mass spectrum over a smoothly falling background. The background is estimated with an innovative data-driven method based on orthonormal functions. The observed $b$-tagged dijet invariant mass spectrum is compatible with the background-only hypothesis. Upper limits at 95% confidence level on a heavy vector-boson production cross section times branching ratio to a pair of $b$-quarks are derived.